BFS simple code solution 20ms


  • 0
    L
    public class Solution {
        public boolean hasPath(int[][] maze, int[] start, int[] destination) {
            int m = maze.length, n = maze[0].length;
            Queue<int[]> q = new LinkedList<>();
            boolean[][] visited = new boolean[m][n];
            int[] delta = {-1, 0, 1, 0, -1};
            
            q.offer(start);
            visited[start[0]][start[1]] = true;
            
            while(!q.isEmpty()) {
                int[] cur = q.poll();
                if(Arrays.equals(cur, destination)) {
                    return true;
                }
    
                for(int k = 0; k < 4; k++) {
                    int i = cur[0], j = cur[1];
                    while(i + delta[k] >= 0 && i + delta[k] < m && 
                          j + delta[k + 1] >= 0 && j + delta[k + 1] < n && 
                          maze[i + delta[k]][j + delta[k + 1]] == 0) {
                        i += delta[k];
                        j += delta[k + 1];
                    }
                    
                    if(!visited[i][j]) {
                        visited[i][j] = true;
                        q.offer(new int[] {i, j});
                    }   
                }
            }
            
            return false;
        }
    }
    

Log in to reply
 

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