Easy-understanding Java DFS solution


  • 0
    T

    First time to post a solution. Not sure it is a good one.

    public boolean hasPath(int[][] maze, int[] start, int[] destination) {
            if(maze==null || maze.length==0 || maze[0].length == 0)
            {
                return false;
            }
           
            if(start[0]==destination[0] && start[1] == destination[1])
            {
            	return true;
            }
            int[][] dirs = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
            int x=start[0], y=start[1];
            for(int[] dir : dirs)
            {
            	maze[x][y]=2;
                int[] curr = findNext(start, dir, maze);
                if( (curr[0]!=x || curr[1]!=y) && hasPath(maze, curr, destination))
                {
                    return true;
                }
            }
            return false;
        }
     
        public int[] findNext(int[] curr, int[] dir, int[][] maze)
        {
            int x=curr[0], y=curr[1];
            int m=maze.length, n=maze[0].length;
            while(x+dir[0] >=0 && x+dir[0]<m && y+dir[1]>=0 && y+dir[1]<n 
            		&& maze[x+dir[0]][y+dir[1]] != 1)
            {
            	if(maze[x+dir[0]][y+dir[1]] == 2)
            	{
            		x=curr[0];
            		y=curr[1];
            		break;
            	}
                   x+=dir[0];
                   y+=dir[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.