542. 01 Matrix

发表于 | 分类于

Given a matrix consists of 0 and 1, find the distance of the nearest 0 for each cell.

The distance between two adjacent cells is 1.
Example 1:
Input:

1
2
3
0 0 0
0 1 0
0 0 0

Output:

1
2
3
0 0 0
0 1 0
0 0 0

Example 2:
Input:

1
2
3
0 0 0
0 1 0
1 1 1

Output:

1
2
3
0 0 0
0 1 0
1 2 1

Note:
The number of elements of the given matrix will not exceed 10,000.
There are at least one 0 in the given matrix.
The cells are adjacent in only four directions: up, down, left and right.

解法1： BFS

这题和那个continental divide的题的思路有点相似的地方。要反过来想问题会变简单。
题意是让我们计算每一个1距离最近的0的距离。如果反过来想，我们从每一个0出发，探查四周，如果当前距离比之前的距离要短，那么更新那个单元格的数值，同时把那个单元格加入到探查的路径中。如果距离要更长，则这一支不需要再探查了。
C++

1

Java

1
2
<!--4-->