[C++] Fast, clear and concise code, O(n)-time and space


  • 0
    class Solution {
    public:
        bool hasPath(vector<vector<int>> &maze, vector<int> &start, vector<int>  &destination) {
            destrow = destination[0];
            destcol = destination[1];
            for (int dir = 0; dir < 4; dir++)
                if (visit_and_move(maze, start[0], start[1], dir))
                    return true;
            return false;
        }
    private:
        int destrow, destcol;
        bool visited [100][100][4];
        int dr [4] = {-1, 1, 0, 0}; // delta row: {up, down, left, right}
        int dc [4] = {0, 0, -1, 1}; // delta col: {up, down, left, right}
        
        bool isWall(vector<vector<int>>& maze, int row, int col) {
            return row < 0 || row >= maze.size() || 
                   col < 0 || col >= maze[0].size() || maze[row][col];
        }
    
        bool visit_and_move(vector<vector<int>>& maze, int row, int col, int dir) {
            int newrow = row + dr[dir];
            int newcol = col + dc[dir];
            if (row == destrow && col == destcol && isWall(maze, newrow, newcol)) 
                return true;
            if (visited[row][col][dir]) 
                return false;
            
            visited[row][col][dir] = true;
            if (!isWall(maze, newrow, newcol))
                return visit_and_move(maze, newrow, newcol, dir);
            for (dir = 0; dir < 4; dir++) {
                if (!visited[row][col][dir]) {
                    visited[row][col][dir] = true;
                    newrow = row + dr[dir];
                    newcol = col + dc[dir];
                    if (!isWall(maze, newrow, newcol) && visit_and_move(maze, newrow, newcol, dir))
                        return true;
                }
            }
            return false;
        }
    };
    

Log in to reply
 

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