my solution with explanation


  • 0
    X
        public boolean hasPath(int[][] maze, int[] start, int[] destination) {
            int m = maze.length;
            int n = maze[0].length;
            boolean[][] visited = new boolean[m][n];
            return helper(maze, visited, start[0], start[1], destination[0], destination[1]);
        }
        
        public boolean helper(int[][] maze, boolean[][] visited, int curX, int curY, int desX, int desY){
            if(visited[curX][curY]) return false;
            visited[curX][curY] = true;
            if(curX == desX && curY == desY) return true;
            int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
            for(int[] dir: directions){
                int tmpX = curX, tmpY = curY;
                while(tmpX + dir[0] >= 0 && tmpX + dir[0] < maze.length && tmpY + dir[1] >= 0 && tmpY + dir[1] < maze[0].length && maze[tmpX +  dir[0]][tmpY + dir[1]] == 0){
                    tmpX += dir[0];
                    tmpY += dir[1];
                }
                if(tmpX != curX || tmpY != curY){
                    if(helper(maze, visited, tmpX, tmpY, desX, desY)) return true;
                }
            }
            // visited[curX][curY] = true;
            return false;
        }
    }
    

    this question is not that hard to think about but has some corner cases to consider and need to think deeply about the function stack,
    if I put visited[][] = true at the slashed place, it will cause stack overflow.


Log in to reply
 

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