# BFS solution with a distance map

• ``````public int shortestDistance(int[][] grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0) return 0;
int m = grid.length, n = grid[0].length;
int[][] dis = new int[m][n];
boolean[][] noreach = new boolean[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
bfs(dis, grid, noreach, i, j);
}
}
}
int res = Integer.MAX_VALUE;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 0 && !noreach[i][j]) res = Math.min(res, dis[i][j]);
}
}
return res == Integer.MAX_VALUE ? -1: res;
}
public void bfs(int[][] dis, int[][] grid, boolean[][] noreach, int i, int j) {
boolean[][] visit = new boolean[grid.length][grid[0].length];
pair p = new pair(i, j);
int value = -1;
while (!q.isEmpty()) {
value++;
int size = q.size();
for (int k = 0; k < size; k++) {
p = q.remove();
int x = p.x;
int y = p.y;
dis[x][y] += value;
if (x-1 >=0 && grid[x-1][y] == 0 && !visit[x-1][y]) {
visit[x-1][y] = true;
}
if (x+1 < grid.length && grid[x+1][y] == 0 && !visit[x+1][y]) {
visit[x+1][y] = true;
}
if (y-1 >=0 && grid[x][y-1] == 0 && !visit[x][y-1]) {
visit[x][y-1] = true;
}
if (y+1 < grid[0].length && grid[x][y+1] == 0 && !visit[x][y+1]) {
visit[x][y+1] = true;
}
}
}
for (int x = 0; x < grid.length; x++) {
for (int y = 0; y < grid[0].length; y++) {
if (!visit[x][y] && grid[x][y] == 0) noreach[x][y] = true;
}
}
}
public class pair{
int x;
int y;
public pair(int i, int j) {
x = i;
y = j;
}
}``````

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