clean java DFS--use a wrap matrix


  • 0
    G
    public class Solution {
        public boolean hasPath(int[][] maze, int[] start, int[] destination) {
            int h = maze.length;
            int w = maze[0].length;
            int[][] matrix = new int[h+2][w+2];//This matrix wrap the maze in the center, the four bounder are built with 1.
            boolean[][] visited = new boolean[h+2][w+2];
            
            for(int i=0;i<h+2;i++){
                for(int j=0;j<w+2;j++){
                    matrix[i][j]=1;
                }
            }
            
            for(int i=1;i<h+1;i++){
                for(int j=1;j<w+1;j++){
                    matrix[i][j]=maze[i-1][j-1];
                }
            }
            
            
            int y = start[0]+1;
            int x = start[1]+1;
            
            return dfs(matrix, y, x, destination, visited);
                
        }
        
        int[][] dirs = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
        
        public boolean dfs(int[][] matrix, int y, int x, int[] ndes, boolean[][] visited){
            if(y==ndes[0]+1 && x==ndes[1]+1){
                return true;
            }
            
            if(visited[y][x]==true){//if the ball come back, false,
                return false;
            }
            
            visited[y][x]=true;
            boolean res = false;
            
            for(int[] temp:dirs){
                
                int tpx = x;
                int tpy = y;
                
                while(matrix[tpy+temp[0]][tpx+temp[1]]!=1){
                    tpy +=temp[0];
                    tpx +=temp[1];
                }
                
                if(visited[tpy][tpx]!=true){
                    res = res|dfs(matrix, tpy, tpx, ndes, visited);
                }
                
            }
            
            return res;    
            
        }
    }

Log in to reply
 

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