Practice › Graphs
Distance of Nearest Zero
Medium · Graphs · Asked at Amazon, Google, Microsoft, Uber
The matrix contains 0s and 1s (at least one 0). For every cell, print the distance to the nearest 0, moving up, down, left or right (each move costs 1).
Input
First line: r c. Next r lines: c values (0 or 1).
Output
The distance matrix, r lines.
Constraints
- 1 ≤ r · c ≤ 10^5
Multi-source BFS: start with every 0 in the queue at distance 0.
Example 1
Input
3 3 0 0 0 0 1 0 0 0 0
Output
0 0 0 0 1 0 0 0 0
Example 2
Input
3 3 0 0 0 0 1 0 1 1 1
Output
0 0 0 0 1 0 1 2 1
Hints
- Running a BFS from every 1 is too slow.
- Run one BFS that starts from all 0s at once (multi-source). The first time a cell is reached, that is its distance to the nearest 0.
Approach
Initialise dist = 0 for every 0 cell and push all of them into the queue; mark 1 cells as unvisited (−1). Standard BFS: when popping a cell, every unvisited neighbour gets dist + 1 and is pushed. Because all sources start at layer 0, each cell is reached first from its closest 0.
Complexity: O(r · c) time · O(r · c) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int R, C;
cin >> R >> C;
vector<vector<int>> d(R, vector<int>(C));
queue<pair<int, int>> q;
for (int i = 0; i < R; i++)
for (int j = 0; j < C; j++) {
int x;
cin >> x;
d[i][j] = x == 0 ? 0 : -1;
if (x == 0) q.push({i, j});
}
int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};
while (!q.empty()) {
int x = q.front().first, y = q.front().second;
q.pop();
for (int k = 0; k < 4; k++) {
int a = x + dx[k], b = y + dy[k];
if (a >= 0 && b >= 0 && a < R && b < C && d[a][b] == -1) d[a][b] = d[x][y] + 1, q.push({a, b});
}
}
for (auto &row : d)
for (int j = 0; j < C; j++) cout << row[j] << (j + 1 < C ? " " : "\n");
return 0;
}Python solution
import sys
from collections import deque
data = list(map(int, sys.stdin.read().split()))
R, C = data[0], data[1]
cells = data[2:]
d = [[0 if cells[i * C + j] == 0 else -1 for j in range(C)] for i in range(R)]
q = deque((i, j) for i in range(R) for j in range(C) if d[i][j] == 0)
while q:
x, y = q.popleft()
for a, b in ((x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)):
if 0 <= a < R and 0 <= b < C and d[a][b] == -1:
d[a][b] = d[x][y] + 1
q.append((a, b))
print("\n".join(" ".join(map(str, row)) for row in d))Java solution
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
in.nextToken();
int R = (int) in.nval;
in.nextToken();
int C = (int) in.nval;
int[][] d = new int[R][C];
ArrayDeque<int[]> q = new ArrayDeque<>();
for (int i = 0; i < R; i++)
for (int j = 0; j < C; j++) {
in.nextToken();
d[i][j] = (int) in.nval == 0 ? 0 : -1;
if (d[i][j] == 0) q.add(new int[] {i, j});
}
int[] dx = {1, -1, 0, 0}, dy = {0, 0, 1, -1};
while (!q.isEmpty()) {
int[] p = q.poll();
for (int k = 0; k < 4; k++) {
int a = p[0] + dx[k], b = p[1] + dy[k];
if (a >= 0 && b >= 0 && a < R && b < C && d[a][b] == -1) {
d[a][b] = d[p[0]][p[1]] + 1;
q.add(new int[] {a, b});
}
}
}
StringBuilder sb = new StringBuilder();
for (int[] row : d) {
for (int j = 0; j < C; j++) sb.append(row[j]).append(j + 1 < C ? " " : "\n");
}
System.out.print(sb);
}
}Solve Distance of Nearest Zero online · All practice problems