beats 99.27%(25ms) DFS without extra two-dimesion "visited" array and "helper" function


  • 0
    X

    I'm surprised that many solutions based on DFS create extra two-dimesion array to store "visited". Actually, we don't need it.

    class Solution {
    public:
        bool hasPath(vector<vector<int>>& maze, vector<int>& start, vector<int>& destination) {
            if (start == destination) return true;
            int r = start[0], c = start[1];
            maze[r][c] = -1;
            int i = r, m = maze.size(), n = maze.front().size();
    
            for (; i > 0 && maze[i - 1][c] != 1; --i); //up
            vector<int> next { i, c };
            if (i != r && maze[i][c] != -1 && hasPath(maze, next, destination)) return true;
    
            for (i = r; i < m - 1 && maze[i + 1][c] != 1; ++i); //down
            next[0] = i;
            if (i != r && maze[i][c] != -1 && hasPath(maze, next, destination)) return true;
    
            for (i = c; i > 0 && maze[r][i - 1] != 1; --i); //left
            next[0] = r; next[1] = i;
            if (i != c && maze[r][i] != -1 && hasPath(maze, next, destination)) return true;
    
            for (i = c; i < n - 1 && maze[r][i + 1] != 1; ++i); //right
            next[1] = i;
            if (i != c && maze[r][i] != -1 && hasPath(maze, next, destination)) return true;
    
            return false;
        }
    };
    

    Or (beats 92.48%(26ms)):

    class Solution {
    public:
        bool hasPath(vector<vector<int>>& maze, vector<int>& start, vector<int>& destination) {
            if (start == destination) return true;
            int r = start[0], c = start[1];
            maze[r][c] = -1;
            int m = maze.size(), n = maze.front().size();
    
            vector<int> next(2);
            for (auto &dr: dirs) {
                int i = r, j = c, nx = dr[0], ny = dr[1];
                while (i + nx >= 0 && i + nx < m && j + ny >= 0 && j + ny < n && maze[i + nx][j + ny] != 1) {
                    i += nx; j += ny;
                }
                next[0] = i; next[1] = j;
                if ((i != r || j != c) && maze[i][j] != -1 && hasPath(maze, next, destination)) return true;
            }
            return false;
        }
    private:
        vector<vector<int>> dirs { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
    };
    

Log in to reply
 

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