# BFS Java Solution

• ``````    private class Pos{
int i, j;
public Pos(int x, int y) {
i = x;
j = y;
}
}
public int shortestDistance(int[][] grid) {
if (grid == null || grid.length == 0) return -1;
int m = grid.length, n = grid[0].length;
int[] dx = {-1, 1, 0, 0}, dy = {0, 0, -1, 1};
int num0 = 0, num1 = 0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == 1) ++num1;
}
}
int min = Integer.MAX_VALUE;
boolean found = false;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == 0) {
int sum = bfs(grid, i, j, new boolean[m][n], dx, dy, num1);
if (sum > 0) {
found = true;
min = Math.min(min, sum);
}
}
}
}
return found ? min : -1;
}
private int bfs(int[][] grid, int i, int j, boolean[][] seen, int[] dx, int[] dy, int num1) {
int cnt = 0, sum = 0;
seen[i][j] = true;
q.offer(new Pos(i, j));
int dis = 0;
while (!q.isEmpty()) {
int size = q.size();
++dis;
for (int k = 0; k < size; ++k) {
Pos pos = q.poll();
for (int di = 0; di < dx.length; ++di) {
int x = pos.i + dx[di], y = pos.j + dy[di];
if (x >= 0 && x < grid.length && y >= 0 && y < grid[x].length && !seen[x][y]) {
if (grid[x][y] == 1) {
sum += dis;
++cnt;
}
else if (grid[x][y] == 0) q.offer(new Pos(x, y));
seen[x][y] = true;
}
}
}
}
if (cnt != num1) return -1;
return sum;
}
``````

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