# Simple Java solution and no priority queue beats 90%

• I did not use priority queue and just use a 2D distance array to record the minimum distance to reach here. It beats 90%. The idea is only the shortest path can get to next search iteration.

``````private final static int[][] dirs = new int[][]{{0,1},{0,-1},{1,0},{-1,0}};
public int shortestDistance(int[][] maze, int[] start, int[] destination) {
if (maze == null) return 0;
// bfs
int m = maze.length;
int n = maze[0].length;
int[][] dist = new int[m][n]; /* record the minimum distance to reach here */
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
dist[i][j] = Integer.MAX_VALUE;
}
}

dist[start[0]][start[1]] = 0;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
int[] curStop = queue.poll();
for (int[] dir : dirs) {
int x = curStop[0] + dir[0];
int y = curStop[1] + dir[1];
while (x >= 0 && x < m && y >= 0 && y < n && maze[x][y] != 1) {
x += dir[0];
y += dir[1];
}
//go back one step
x -= dir[0];
y -= dir[1];
if (x == curStop[0] && y== curStop[1]) continue;
int distFromLast = Math.abs(x - curStop[0]) + Math.abs(y - curStop[1]);
if (distFromLast + dist[curStop[0]][curStop[1]] < dist[x][y]) {
dist[x][y] = dist[curStop[0]][curStop[1]] + distFromLast;