20 lines self-explained dfs java code


  • 0
    U
    public class Solution {
        private void dfs(int[][] maze, int i, int j, int m, int n){
            if(maze[i][j] == 3) return;
            maze[i][j] = 3;
            
            int x;
            //down
            for(x = i ; x < m && maze[x][j] != 1 ; x++);
            dfs(maze, x - 1, j, m, n);
            
            //up
            for(x = i ; x >= 0 && maze[x][j] != 1 ; x--);
            dfs(maze, x + 1, j, m, n);
            
            //right
            for(x = j ; x < n && maze[i][x] != 1 ; x++);
            dfs(maze, i, x - 1, m, n);
            
            //left
            for(x = j ; x >= 0 && maze[i][x] != 1 ; x--);
            dfs(maze, i, x + 1, m, n);
        }
        
        public boolean hasPath(int[][] maze, int[] start, int[] destination) {
            int m = maze.length;
            if(m == 0) return false;
            int n = maze[0].length;
            if(n == 0) return false;
            
            int si = start[0];
            int sj = start[1];
    
            int di = destination[0];
            int dj = destination[1];
    
            dfs(maze, si, sj, m, n);
            
            return maze[di][dj] == 3;
        }
    }
    

Log in to reply
 

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