力扣题解：542题01矩阵 知识点：多源BFS（确定当前遍历层次与否两类模板）用于求最短距离_力扣542

1、题目描述：题目链接
给定一个由 0 和 1 组成的矩阵，找出每个元素到最近的 0 的距离。
两个相邻元素间的距离为 1 。
示例 1:
输入:
0 0 0
0 1 0
0 0 0
输出:
0 0 0
0 1 0
0 0 0
注意:
给定矩阵的元素个数不超过 10000。
给定矩阵中至少有一个元素是 0。
矩阵中的元素只在四个方向上相邻: 上、下、左、右。

2、思路：搞懂题目考察什么，剩下的任务就是套模板！
a) 首先看到在矩阵上搜索距离，思考关于图的解法。
b) 本题给出了一个场景：求每个1到0的最短距离。在一个图中，能从一个点出发求这种最短距离的方法很容易想到就是 BFS，即把周围这一圈搜索完成之后，再搜索下一圈，是慢慢扩大搜索范围的。

2.1、BFS模板：
BFS 使用队列，把每个还没有搜索到的点依次放入队列，然后再弹出队列的头部元素当做当前遍历点。BFS 总共有两个模板：
a）如果不需要确定当前遍历到了哪一层，BFS 模板如下：

while queue 不空：
    cur = queue.pop()
    for 节点 in cur的所有相邻节点：
        if 该节点有效且未访问过：
            queue.push(该节点)
1
2
3
4
5

b）如果要确定当前遍历到了哪一层，BFS 模板如下:
这里增加了 level 表示当前遍历到二叉树中的哪一层了，也可以理解为在一个图中，现在已经走了多少步了。size 表示在当前遍历层有多少个元素，也就是队列中的元素数，我们把这些元素一次性遍历完，即把当前层的所有元素都向外走了一步。

level = 0
while queue 不空：
    size = queue.size() // 记录当前层次
    while (size --) {
        cur = queue.pop()
        for 节点 in cur的所有相邻节点：
            if 该节点有效且未被访问过：
                queue.push(该节点)
    }
    level ++;
1
2
3
4
5
6
7
8
9
10

上面两个是通用模板，在任何题目中都可以用，是要记住的！
思路链接，作者：fuxuemingzhu

3、多源BFS与单源BFS的区别：
3.1、思路：

• 对于 「Tree 的 BFS」（典型的「单源 BFS」） 大家都已经轻车熟路了：
  首先把 root 节点入队，再一层一层无脑遍历就行了。
• 对于 「图 的 BFS」 （「多源 BFS」） ，与 「Tree 的 BFS」的区别注意以下两条：
  Tree 只有 1 个 root，而图可以有多个源点，所以首先需要把多个源点都入队；
  Tree 是有向的因此不需要标识是否访问过，而对于无向图来说，必须得标志是否访问过哦！并且为了防止某个节点多次入队，需要在其入队之前就将其设置成已访问！
  思路链接，作者：sweetiee

3.2、源点查找：

• 对于Tree：
  源点就是树根。
• 对于图：
  图的遍历可以从任意一点开始，但对于多源问题，首先遍历全部顶点找出所有源点都push进队列中。

4、C++代码：
代码是记录自己的思路，时间复杂度与空间复杂度都不是最优的，最优的代码见上述两个链接。

class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
        int row = matrix.size();
        int col = matrix[0].size();
        vector<vector<int>> res(row,vector<int>(col)); //记录结果
        vector<vector<int>> visited(row,vector<int>(col)); // 记录访问情况
        queue<pair<int,int>> q;
        for(int i = 0;i<row; i++){ //首先查找所有源点
            for(int j = 0;j<col; j++){
                if(matrix[i][j] == 0){                   
                    q.push(make_pair(i,j));
                    visited[i][j] = 1;
                }
            }
        }
        int val = 0; // 记录遍历层次
        while(!q.empty()){
            int size = q.size(); //记录每一层元素个数
            for(int i = 0;i<size;i++){
                pair<int, int> tmp = q.front();
                q.pop();
                res[tmp.first][tmp.second] = val;
                if(tmp.first-1>=0 && visited[tmp.first-1][tmp.second] == 0){
                    q.push(make_pair(tmp.first-1,tmp.second));
                    visited[tmp.first-1][tmp.second] = 1;
                }
                if(tmp.first+1<row && visited[tmp.first+1][tmp.second] == 0){
                    q.push(make_pair(tmp.first+1,tmp.second));
                    visited[tmp.first+1][tmp.second] = 1;
                }
                if(tmp.second-1>=0 && visited[tmp.first][tmp.second-1] == 0){
                    q.push(make_pair(tmp.first,tmp.second-1));
                    visited[tmp.first][tmp.second-1] = 1;
                }
                if(tmp.second+1<col && visited[tmp.first][tmp.second+1] == 0){
                    q.push(make_pair(tmp.first,tmp.second+1));
                    visited[tmp.first][tmp.second+1] = 1;
                }
            }
            val++;
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

总结：

1、求距离一般是图的问题，思考图的解法。
2、最短距离常用BFS进行求解。
3、多源BFS首先查找所有源点。
4、记住上述BFS确定当前遍历层次的做法。