Java AC solution DFS


  • 0
    public boolean hasPath(int[][] maze, int[] start, int[] destination) {
        boolean[][][] map = new boolean [maze.length][maze [0].length][4];
        return roll (map, maze, start, destination);
    }
        
    int [] rowdir = { 0, 1,  0, -1 };
    int [] coldir = { 1, 0, -1,  0 };
        
    private boolean roll (boolean[][][] map, int[][] maze, int[] start, int[] destination) {
        for (int idx = 0; idx < 4; idx ++) {
            if (!map [start [0]][start [1]][idx]) {
                map [start [0]][start [1]][idx] = true;
                if (maze [start [0]][start [1]] == 1) continue;
                int [] next = new int [] { start [0], start [1] };
                    
                while (next [0] >= 0 && next [0] < maze.length && next [1] >= 0 && next [1] < maze[0].length && maze [next [0]][next [1]] == 0)  {
                    next [0] += rowdir [idx]; 
                    next [1] += coldir [idx];
                }
                    
                next [0] = Math.max (0, next [0]);
                next [1] = Math.max (0, next [1]);
                next [0] = Math.min (maze.length - 1, next [0]);
                next [1] = Math.min (maze [0].length - 1, next [1]);
                    
                if (maze [next [0]][next [1]] == 1) { next [0] -= rowdir [idx]; next [1] -= coldir [idx]; }
                if ((next [0] == destination [0] && next [1] == destination [1]) || (roll (map, maze, next, destination))) return true;
            }
        }
        return false;
    }
    

Log in to reply
 

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