Short and Clean Java dfs solution.


  • 0
    H
    public class Solution {
        public boolean hasPath(int[][] maze, int[] start, int[] destination) {
              boolean[][] visited = new boolean[maze.length][maze[0].length];
            return helper(maze,start[0]+1,start[1],destination,new int[]{1,0},visited) ||
                    helper(maze,start[0]-1,start[1],destination,new int[]{-1,0},visited)||
                    helper(maze,start[0],start[1]-1,destination,new int[]{0,-1},visited)||
                    helper(maze,start[0],start[1]+1,destination,new int[]{0,1},visited);
        }
    
    
        public boolean helper(int [][] maze, int startx, int starty, int []destination, int[] ori, boolean [][]visited){
            if(startx < 0 || startx >= maze.length || starty < 0 || starty >= maze[0].length || maze[startx][starty] == 1)
                return false;
    
    
            if((startx+ori[0] != startx && (startx+ori[0] == -1 || startx+ori[0]  == maze.length)) || 
                    (starty+ori[1] != starty && (starty+ori[1] == -1 || starty+ori[1]  == maze[0].length)) ||maze[startx+ori[0]][starty+ori[1]] == 1 ){
                if(startx == destination[0] && starty == destination[1]) return true;
                if(visited[startx][starty]) return false;
                visited[startx][starty] = true;
                return helper(maze,startx+1,starty,destination,new int[]{1,0},visited) ||
                        helper(maze,startx-1,starty,destination,new int[]{-1,0},visited)||
                        helper(maze,startx,starty-1,destination,new int[]{0,-1},visited)||
                        helper(maze,startx,starty+1,destination,new int[]{0,1},visited);
    
            }
    
            return helper(maze,startx+ori[0],starty+ori[1],destination,ori,visited);
    
    
        }
    }
    
    

Log in to reply
 

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