Simple BFS logic Java


  • 0
    W

    Auxiliary class Point is a little verbose but should be easy to understand. The main thing is to figure out the possible next position.

    class Solution {
        int[] directions = {0, 1, 0, -1, 0}; // rowIndex: 0-3, colIndex: rowIndex + 1
    
        public int shortestDistance(int[][] maze, int[] start, int[] destination) {
            Queue<Point> queue = new ArrayDeque<>();
            Point initialPoint = new Point(start[0], start[1]);
            queue.offer(initialPoint);
            int steps = 0;
            
            // same point should not be passed through in the same direction
            boolean[][][] visited = new boolean[maze.length][maze[0].length][4];
            while (!queue.isEmpty()) {
                int queueSize = queue.size();
                for (int i = 0; i < queueSize; i ++) {
                    Point p = queue.poll();
                    if (p.row == destination[0] && p.col == destination[1]) {
                        // check if the same direction next point is a wall, then we land on destination
                        Point np = new Point(
                            p.row + directions[p.direction],
                            p.col + directions[p.direction + 1],
                            p.direction
                            );
    
                        if (np.isWall(maze)) return steps;
                    }
                    List<Point> nextPoints = p.nextPoints(maze);
                    for (Point np : nextPoints) {
                        if (!visited[np.row][np.col][np.direction]) {
                            queue.offer(np);
                        }
                    }
                    if (p.direction >= 0) visited[p.row][p.col][p.direction] = true;
                }
                steps ++;
            }
            return -1;
        }
        
        
        class Point {
            int row;
            int col;
            int direction;
            public Point(int i, int j, int d) {
                row = i;
                col = j;
                direction = d;
            }
            public Point(int i, int j) {
                row = i;
                col = j;
                direction = -1; // no direction
            }
            int getBounceBackDirection() {
                return direction == -1 ? -1 : (direction + 2) % 4;
            }
            
            List<Point> nextPoints(int[][] maze) {
                List<Point> result = new ArrayList<>();
                // if this does not have any direction, it could be any,
                // as long as it's not a wall
                if (direction < 0) {
                    for (int i = 0; i < 4; i ++) {
                        int newRow = row + directions[i];
                        int newCol = col + directions[i + 1];
                        Point p = new Point(newRow, newCol, i);
                        if (!p.isWall(maze)) result.add(p);
                    }
                } else {
                    // already has direction, can only keep going in 
                    // the same direction, unless it's a wall
                    Point sameDirectionNextP = new Point(
                        row + directions[direction],
                        col + directions[direction + 1],
                        direction
                    );
                    if (sameDirectionNextP.isWall(maze)) {
                        for (int i = 0; i < 4; i ++) {
                            if (i == direction || i == getBounceBackDirection()) continue;
                        
                            int newRow = row + directions[i];
                            int newCol = col + directions[i + 1];
                            Point p = new Point(newRow, newCol, i);
                            if (!p.isWall(maze)) result.add(p);                        
                        }
                    } else {
                        result.add(sameDirectionNextP);
                    }
                }
                return result;
            }
            
            boolean isWall(int[][] maze) {
                return 
                    row < 0 || row >= maze.length ||
                    col < 0 || col >= maze[0].length ||
                    maze[row][col] == 1;
            }
        }
    }
    

Log in to reply
 

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