# Share a Java implement

• Short version: BFS from every building, calculate the distances and find the minimum distance in the end.

Key optimization : we do not go into a land, if it is not accessible by at least one of previous buildings.

For a long explanation see here in my blog.

It runs in 13 ms.

It is the same idea as stefan's c++ solution. I didn't see it until now. I did this myself.

Also one may want to make a copy of `grid` if it is not suppose to be modified.

Java

``````int[] dx = {1, 0, -1, 0}, dy = {0, 1, 0, -1};

public int shortestDistance(int[][] grid) {
int m = grid.length, n = grid[0].length;
int[][] dist = new int[m][n];
// Initialize building list and accessibility matrix `grid`
List<Tuple> buildings = new ArrayList<>();
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j) {
if (grid[i][j] == 1)
grid[i][j] = -grid[i][j];
}
// BFS from every building
for (int k = 0; k < buildings.size(); ++k)
bfs(buildings.get(k), k, dist, grid, m, n);
// Find the minimum distance
int ans = -1;
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
if (grid[i][j] == buildings.size() && (ans < 0 || dist[i][j] < ans))
ans = dist[i][j];
return ans;
}

public void bfs(Tuple root, int k, int[][] dist, int[][] grid, int m, int n) {
Queue<Tuple> q = new ArrayDeque<>();
while (!q.isEmpty()) {
Tuple b = q.poll();
dist[b.y][b.x] += b.dist;
for (int i = 0; i < 4; ++i) {
int x = b.x + dx[i], y = b.y + dy[i];
if (y >= 0 && x >= 0 && y < m && x < n && grid[y][x] == k) {
grid[y][x] = k + 1;
q.add(new Tuple(y, x, b.dist + 1));
}
}
}
}
class Tuple {
public int y;
public int x;
public int dist;

public Tuple(int y, int x, int dist) {
this.y = y;
this.x = x;
this.dist = dist;
}
}
// 72 / 72 test cases passed.
// Status: Accepted
// Runtime: 13 ms
// 99.22%``````

• Awesome optimization!

• your link of blog is not working now. I really want to see it. It has always been a good place to study. Will you please fix the blog. I appreciate it.

• I updated the wordpress theme...and then it crashed...
No idea why....

• it says algobox.org is currently unable to handle this request

• yes i know. I am working on it.

• It's ok now.

• Its again down and it says "Error establishing a database connection"

• Why did u write it in this way `dist[b.y][b.x] += b.dist;`? Why no just `x, y` instead of `y, x`? Is there any special meaning in it?

Basically, in BFS, you reversed all `x` and `y`, because you use x to be y and y to be x in `Tuple`, I cannot figure out why.

• @zhugejunwei Same question

• @dietpepsi said in Share a Java implement:

grid[y][x] == k

This is my favorite part of this code, which can not only eliminates unnecessary exploration of grids that cannot be reached by any of previous buildings, but also avoid using boolean[][] visited array to record visited grids. Thanks a lot :)

• @bobw Can you explain the purpose of this equation? I'm not sure I get the point. Is it used to count the number of reachable buildings so far(not all, only the previous ones)?

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