Shorter DFS Java solution


  • 0
    G

    Not a subscriber, only tested with limited test cases. So correctness of this solution is not guaranteed.

    public class TheMaze {
    
        private final int[][] direction = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        public boolean hasPath(int[][] maze, int[] start, int[] destination) {
            if (maze[start[0]][start[1]] == 2)
                return false;
            if (Arrays.equals(start, destination))
                return true;
            maze[start[0]][start[1]] = 2;
            for (int[] d : direction) {
                int[] stop = roll(d, start, maze);
                if (hasPath(maze, stop, destination))
                    return true;
            }
    
            return false;
    
        }
    
        private int[] roll(int[] d, int[] start, int[][] maze) {
    
            int x = start[0], y = start[1], tx = x + d[0], ty = y + d[1];
            while (tx < maze.length && tx >= 0 && ty < maze[0].length && ty >= 0
                && maze[tx][ty] != 1// could be 0 or 2
                ) {
                x = tx;
                y = ty;
                tx += d[0];
                ty += d[1];
            }
            return new int[] {x, y};
        }
    }
    

Log in to reply
 

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