clean java DFS--use a wrap matrix

  • 0
    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++){
            for(int i=1;i<h+1;i++){
                for(int j=1;j<w+1;j++){
            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;
            boolean res = false;
            for(int[] temp:dirs){
                int tpx = x;
                int tpy = y;
                    tpy +=temp[0];
                    tpx +=temp[1];
                    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.