# Simple BFS logic Java

• 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);
}
} 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);
}
} else {
}
}
return result;
}

boolean isWall(int[][] maze) {
return
row < 0 || row >= maze.length ||
col < 0 || col >= maze[0].length ||
maze[row][col] == 1;
}
}
}
``````

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