Java BFS solution


  • 0
    T
    public class Solution {
        private static final int[] POINT = {0, 1, 0, -1, 0};
        public boolean hasPath(int[][] maze, int[] start, int[] destination) {
            if(maze == null || maze.length == 0 || start == null || destination == null){
                return false;
            }
            // initial state
            if(start[0] == destination[0] && start[1] == destination[1]){
                return true;
            }
            int rows = maze.length;
            int cols = maze[0].length;
            boolean[][] visited = new boolean[rows][cols];
            Queue<Integer> queue = new LinkedList<>();
            queue.offer(start[0] * cols + start[1]);
            visited[start[0]][start[1]] = true;
            while(!queue.isEmpty()){
                int tmp = queue.poll();
                int row = tmp / cols;
                int col = tmp % cols;
                for(int i = 0; i < 4; i++){
                    int newRow = row;
                    int newCol = col;
                    // hit the wall
                    while(newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols && maze[newRow][newCol] == 0){
                        newRow += POINT[i];
                        newCol += POINT[i + 1];
                    }
                    newRow -= POINT[i];
                    newCol -= POINT[i + 1];
                    if(!visited[newRow][newCol]){
                        visited[newRow][newCol] = true;
                        if(newRow == destination[0] && newCol == destination[1]){
                            return true;
                        }
                    queue.offer(newRow * cols + newCol);
                    }
                    
                }
            }
            return false;
        }
    }
    

Log in to reply
 

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