25ms C++ DFS solution with path pruning


  • 0
    H

    The idea is simple. Just try every path and pruning by round_trip and length check. Comments inline.

    class Solution {
    public:
        string findShortestWay(vector<vector<int>>& maze, vector<int>& ball, vector<int>& hole) {
            int m = maze.size();
            if (m == 0) return "invalid";
            int n = maze[0].size();
            vector<string> res;
            int len = m * n; // max possible distance
            vector<vector<int>> visited(m, vector<int>(n));
            visited[ball[0]][ball[1]] = true;
            dfs(maze, visited, "", ball[0], ball[1], hole, 0, len, res);
            if (res.empty()) return "impossible";
            sort(res.begin(), res.end());
            return res[0];
        }
        
        void dfs(vector<vector<int>>& maze, vector<vector<int>>& visited, string p,
                int row, int col, vector<int>& hole, int cur, int& len, vector<string>& path ) {
            int m = maze.size();
            int n = maze[0].size();
            vector<int> inc = { 0, 1, 0, -1, 0 }; // four directions
            vector<char> dir = {'r', 'd', 'l', 'u'};
            for (int i = 0; i < 4; i++) {
                int x = inc[i], y = inc[i+1];
                int cur_r = row, cur_c = col;
                bool boomerang = false; // help pruning
                // rolling to walls in four directions
                while (cur_r+x >= 0 && cur_r+x < m && cur_c+y >= 0 && cur_c+y < n && maze[cur_r+x][cur_c+y] == 0) {
                    cur_r += x;
                    cur_c += y;
                    if (visited[cur_r][cur_c]) {
                        boomerang = true; // we are backing to passed way, it won't be shortest at all
                        break;
                    }
                    // passing the hole, validate and put result
                    if (cur_r == hole[0] && cur_c == hole[1]) {
                        cur += abs(cur_r - row) + abs(cur_c - col);
                        if (cur < len) {
                            path.clear();
                            len = cur;
                        }
                        if (cur == len) path.push_back(p + dir[i]);  
                        return;
                    }
                }
                if (boomerang) continue;
                int cur_l = cur + abs(cur_r - row) + abs(cur_c - col);
                // proceed if the point is not visited and still possible to get shorter distance
                if (!visited[cur_r][cur_c] && cur_l < len) {
                    visited[cur_r][cur_c] = 1;
                    dfs(maze, visited, p+dir[i], cur_r, cur_c, hole, cur_l, len, path);
                    visited[cur_r][cur_c] = 0;
                }
            }
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.