994. 腐烂的橘子（树/图的BFS问题）
解题思路:
多源BFS
，首选找到
所有的腐烂的橘子
，放入队列中，然后进行
BFS
广搜，广搜的
层数 - 1
就是所需要花费的分钟数。
在最开始先扫描一遍二维数组，将所有的
腐烂的橘子
加入
队列
，同时统计新鲜橘子的数量
freshCount
，
如果扫描完毕发现没有找到
腐烂的橘子
，则此时可以直接确定答案：若
freshCount>0
则答案为
-1
（不可能全部腐烂），否则答案为
0
（即
0
分钟时就没有新鲜的橘子了）。
如果有找到
腐烂的橘子
，则进行
按层
BFS
，每次取出队列的大小，访问这一层的每个腐烂的橘子，
在每一层中，查看腐烂橘子的四个方向的邻居，如果
邻居未越界且
是新鲜的橘子，就将其腐烂，并入队，同时将
freshCount - 1
。
在访问完一层后，层索引 level++。
最终看
freshCount
是否还有剩余，如果还有
剩余，
说明还存在新鲜橘子，答案为
-1
（没能全部腐烂）
，否则答案为
level - 1
(
最后一层会腐烂0个橘子
) 。
在第 5 次 BFS 中会腐烂 0 个橘子，然后退出BFS的循环，上图没有画出（注：第 4 次 BFS 中会将上图中最后一个橙黄色的 2 入队，进入第 5 次 BFS 时，会取出这个 2 然后发现它周围没有橘子可腐烂了，此时退出整个BFS）。所以总共会执行 5 层BFS搜索，但只需要 4 分钟即可全部腐烂完毕。因此答案是 level - 1。
542. 01 矩阵（树/图的BFS问题）
解题思路:
1.
多源BFS
，类似994.腐烂的橘子，对于矩阵中的每一个元素，如果是
0
，那么离它最近的
0
就是它自己，因此
0
的位置距离是
0
。
因此可以
从所有的 0 开始出发进行 BFS，寻找未访问过的 1
，并将该位置的
距离
设置为当前
BFS的层数
。
首先遍历一遍矩阵将遇到的
0
全部入队，并标记已访问，然后只要队列不为空，就取出当前队列大小，访问这一层的节点，
每次取出当前队首的位置，访问它的上下左右四个邻居，如果邻居未访问过且没有越界，就将邻居坐标入队并标记已访问，同时设置邻居的距离值，
到邻居的距离值就是当前搜索的层数
。
注意：标记是否已访问可以使用
boolean[][] visited
数组，也可以在原矩阵上修改，初始时将所有的
1
改成
-1
。
为什么需要
从 0 出发广搜 1
，而不是从 1 出发去广搜 0？
首先矩阵中两个数字之间距离是相互等价的：从 1 到 0 的距离就是从 0 到 1 的距离。
假设10000x10000的矩阵中只有一个0，那么如果从1出发去广搜0的话，需要对剩余所有的1都进行一遍BFS来更新到这个0的距离，也就是需要进行
99,999,999
次BFS。
但是如果我们从这个0出发去广搜1的话，只需要进行
1
次BFS即可知道这个0到每个1的距离（也就是每个1到这个0的距离）。
当矩阵中有很多个0的时候，我们可以把这些 0 看成一个整体的「超级零」，它与矩阵中所有的 0 相连，这样的话，就与矩阵中只有一个 0 的情况一样了，那么怎样才能做到看成一个整体的「超级零」呢？开始就提前把所有的 0 全部加入队列，然后再开始 BFS，这就相当于从这个整体的「超级零」出发向外进行一圈一圈的BFS搜索。
这题代码结构几乎与994. 腐烂的橘子一样，注意两点：
更新答案的时机是在 BFS 搜索将邻居入队的时候，更新的是邻居格子的答案（邻居是值为1的格子）。
需要将统计层数的代码level++放在每一层访问的开头，因为访问该层的邻居节点时就需要使用到层数了，所以需要提前统计。
下面是使用提前将矩阵中的 1 置为 -1 的方式来代替 visited 数组的版本：
因为矩阵中除了 0 就是 1，将所有的 1 置为 -1 后，只需判断遇到的格子只要是 -1 就表示是未访问过的，将该格子的值更新为当前搜索的层数 level 即可。
解题思路:
2.
动态规划
，我们用
dp[i][j]
来表示该位置距离最近的
0
的距离。对于任一点
(i, j)
，距离
0
的距离为：
if matrix[i][j] == 1，f(i, j) = 1 + min(dp(i - 1, j), dp(i, j - 1), dp(i + 1, j), dp(i, j + 1))
if matrix[i][j] == 0，dp(i, j) = 0
我们发现
dp[i][j]
是由其
上下左右
四个状态来决定，无法从一个方向开始递推！
例如被四个
0
包围的
1
，从中心位置的
1
移动到这四个
0
，就需要使用四种不同的方法：
1) 只有
水平向左
移动 和
竖直向上
移动；
2) 只有
水平向左
移动 和
竖直向下
移动；
3) 只有
水平向右
移动 和
竖直向上
移动；
3) 只有
水平向右
移动 和
竖直向下
移动。
因此我们分别从四个角开始递推，就得到了位于
「左上方、右上方、左下方、右下方」
距离
(i,j)
的最近的
0
的距离。
优化：从四个角开始的
4
次递推，还可以优化成从任一组对角开始的
2
次递推，比如只写从
左上角
、
右下角
开始递推就行了。
下面是从左上角开始扫描的流程示意：
为了方便处理for循环中的边界条件判断，我们可以在dp数组的上下左右各添加一行（防御编程思想），并初始化为最大值，
然后就可以省去各种条件判断，处理中间的部分的dp时，只需要考虑左上和右下的最小值+1即可：dp[i][j] = min(dp[i][j], min(左， 上) + 1)
或 dp[i][j] = min(dp[i][j], min(右， 下) + 1)
下面是从左上角开始扫描的流程示意：
此题dp解法较难想到。
1162. 地图分析（树/图的BFS问题）
解题思路:
1.
多源BFS
从陆地出发 向上下左右四周搜索海洋
，搜索的
最大
层数
就是离陆地最远的海洋距离。
首先遍历一遍矩阵，将所有遇到的
陆地
坐标
入队
。结束后判断如果队列大小为
0
，说明全是
海洋
，如果队列大小为
NxN
，说明全是
陆地
，这两种情况都返回
-1
。
然后从陆地开始进行
BFS
，每次取出当前队列大小，计数层数
level++
, 访问这一层的每个节点，每次取出队首元素坐标，然后看四周的邻居坐标，如果是海洋就入队并标记(或利用原数组置为
陆地
)。
最后返回BFS的
层数 - 1
，因为是从陆地出发的，
第一层是陆地
，所以层数要 - 1。（这跟腐烂的橘子求解答案一样）
这题跟542题非常相似，都是反向进行多源BFS，542是从所有的 0 出发找 1，这题是从所有的 1 出发找 0，要寻找的那一方就是题目要更新答案的那一方。
解题思路:
2.
动态规划
，代码跟542. 01 矩阵 dp解法类似，做两次dp，从左上到右下和从右下到左上。
先在dp数组的上下左右各添加一行，以处理边界问题
相关文章
发表评论