PLEASE HELP MY DFS!! Why this got RUN TIME ERROR??


  • 0
    A
    class Solution {
    private:
        void dfs(vector<vector<int> >& maze, vector<int>& start, const vector<int>& destination, 
        vector<vector<bool> >& marked) {
            vector<vector<int> > dirs = {{1, 0}, 
                                       {-1, 0}, 
                                       {0, 1}, 
                                       {0, -1}};
            marked[start[0]][start[1]] = true;
            for (int i = 0; i < 4; ++i) {
                dfs(maze, start, destination, marked, dirs, dirs[i]);
            }
        }
        void dfs(vector<vector<int> >& maze, vector<int> start, const vector<int>& destination,
        vector<vector<bool>>& marked, vector<vector<int> >& dirs, vector<int> cur_dir) {
            if (marked[destination[0]][destination[1]]) return;
            int i = start[0] + cur_dir[0];
            int j = start[1] + cur_dir[1];
            if (i < 0 || j < 0 || i > maze.size() - 1 || j > maze[0].size() - 1 || maze[i][j] == 1) {
                if (!marked[start[0]][start[1]]) {
                    marked[start[0]][start[1]] = true;
                    for (int k = 0; k < 4; ++k) {
                        dfs(maze, start, destination, marked, dirs, dirs[k]);
                    }
                }
            } else {
                vector<int> new_start = {i, j};
                dfs(maze, new_start, destination, marked, dirs, cur_dir);
            }
        }
    public:
        bool hasPath(vector<vector<int> >& maze, vector<int>& start, vector<int>& destination) {
            int rows = maze.size();
            int cols = maze[0].size();
            if (maze.empty() || maze[0].empty()) return false;
            if (start[0] == destination[0] && start[1] == destination[1]) return true;
            if (maze[start[0]][start[1]] == 1 || maze[destination[0]][destination[1]] == 1) return false;
            
            vector<vector<bool>> marked(rows, vector<bool>(cols, false));
            dfs(maze, start, destination, marked);
            return marked[destination[0]][destination[1]];
        }
    };```

Log in to reply
 

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