Clean BFS java solution - 35ms

• ``````public int shortestDistance(int[][] grid) {
if (grid == null || grid.length == 0) {
return -1;
}
int[][] cost = new int[grid.length][grid[0].length];
// Staring from each building, we do BFS and write the cost matrix
for (int i = 0; i < grid.length; i ++) {
for (int j = 0; j < grid[0].length; j ++) {
if (grid[i][j] == 1) {
BFS(grid, cost, i, j);
}
}
}
// Go through the cost matrix to find the minValue that is > 0
int minDistance = Integer.MAX_VALUE;
for (int i = 0; i < cost.length; i ++) {
for (int j = 0; j < cost[0].length; j ++) {
if (grid[i][j] != 2 && grid[i][j] != 1 && cost[i][j] != 0) {
minDistance = Math.min(cost[i][j], minDistance);
}
}
}
return minDistance == Integer.MAX_VALUE? -1: minDistance;
}
private void BFS(int[][] grid, int[][] cost, int starti, int startj) {
int[][] directions = new int[][]{{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
boolean[][] visited = new boolean[grid.length][grid[0].length];
myQueue.offer(Arrays.asList(starti, startj));
visited[starti][startj] = true;
int distance = 0;
while(!myQueue.isEmpty()) {
int size = myQueue.size();
for (int i = 0; i < size; i ++) {
List<Integer> cur = myQueue.poll();
int curX = cur.get(0);
int curY = cur.get(1);
// Fill in distance info to cost[][]
cost[curX][curY] += distance;
// Add next positions into myQueue
for (int[] dir: directions) {
int nextX = curX + dir[0];
int nextY = curY + dir[1];
// If this position is within the range,
// and it is not obstacle or building
// and it is not visited, we cannot visited it.
if (nextX < grid.length && nextX >= 0 && nextY < grid[0].length && nextY >= 0 &&
grid[nextX][nextY] != 2 && grid[nextX][nextY] != 1 &&
visited[nextX][nextY] == false) {
myQueue.offer(Arrays.asList(nextX, nextY));
visited[nextX][nextY] = true;
}
}
}
distance ++;
}
// Mark all the unreachable position as obstacle, because they would never become a valid position.
for (int i = 0; i < cost.length; i ++) {
for (int j = 0; j < cost[0].length; j ++) {
if (grid[i][j] != 1 && grid[i][j] != 2 && visited[i][j] == false) {
grid[i][j] = 2;
}
}
}
}
``````

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