LeetCode 542 01 矩阵(BFS)
题目链接:01 矩阵
给定一个由 0 和 1 组成的矩阵,找出每个元素到最近的 0 的距离。
两个相邻元素间的距离为 1 。
示例 1: 输入:
0 0 0
0 1 0
0 0 0
输出:
0 0 0
0 1 0
0 0 0
示例 2: 输入:
0 0 0
0 1 0
1 1 1
输出:
0 0 0
0 1 0
1 2 1
注意:
- 给定矩阵的元素个数不超过 10000。
- 给定矩阵中至少有一个元素是 0。
- 矩阵中的元素只在四个方向上相邻: 上、下、左、右。
思路
广搜BFS,和 1162 地图分析有点像,题目要求出每个元素与0最近的距离是多少,那么不用问,肯定值为0的点的距离还是0,其余的可以搜出来。
首先把值为0的坐标全部入队,像四个方向搜索,如果是1,当前的步数就+1,如果是0,那步数不变,只需要在搜索的时候,一直给答案的距离与当前步数取最小值即可。
代码
|
|
最后修改于 2020-04-15

本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
0/500
Twikoo Management Panel
Password