# Fast O(m*n) BFS solution with deque

• ``````public int shortestDistance(int[][] maze, int[] start, int[] destination) {
int rows = maze.length;
int cols = 0;
if (rows > 0) {
cols = maze[0].length;
}
boolean[][][] visited = new boolean[rows][cols][4];
Deque<int[]> deque = new ArrayDeque<>();
int[][] dirs = { { 0, 1 }, { 0, -1 }, { -1, 0 }, { 1, 0 } };
//store visited for each direction.
for (int i = 0; i < dirs.length; i++) {
deque.offer(new int[] { start[0], start[1], 0, i });
visited[start[0]][start[1]][i] = true;
}
while (!deque.isEmpty()) {
int[] prev = deque.poll();
int row = prev[0];
int col = prev[1];
int dis = prev[2];
int[] dir = dirs[prev[3]];
if (row + dir[0] >= 0 && col + dir[1] >= 0 && row + dir[0] < rows && col + dir[1] < cols
&& maze[row + dir[0]][col + dir[1]] == 0) {
//not changing direction
row += dir[0];
col += dir[1];
if (!visited[row][col][prev[3]]) {
deque.offer(new int[] { row, col, dis + 1, prev[3] });
visited[row][col][prev[3]] = true;
}
} else {
//changing direction
if (row == destination[0] && col == destination[1]) {
return dis;
}
for (int i = 0; i < dirs.length; i++) {
if (!visited[row][col][i]) {
//push to deque since distance does not change
deque.push(new int[] { row, col, dis, i });
visited[row][col][i] = true;
}
}
}
}
return -1;
}
``````

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