多源BFS问题01-矩阵
【多源BFS问题】01 矩阵
542. 01 矩阵
给定一个由
0
和
1
组成的矩阵
mat
，请输出一个大小相同的矩阵，其中每一个格子是
mat
中对应位置元素到最近的
0
的距离。
两个相邻元素间的距离为
1
。
示例 1：
输入：mat = [[0,0,0],[0,1,0],[0,0,0]]
输出：[[0,0,0],[0,1,0],[0,0,0]]示例 2：
输入：mat = [[0,0,0],[0,1,0],[1,1,1]]
输出：[[0,0,0],[0,1,0],[1,2,1]]提示：
m == mat.lengthn == mat[i].length1 <= m, n <= 1041 <= m * n <= 104mat[i][j] is either 0 or 1.mat中至少有一个0
解题思路：多源 BFS + 正难则反
首先这里用暴力解法肯定会超时，所以就不讲解了！
然后这是我们遇到的第一道多源最短路问题，会讲的详细一点！前面简介说过，多源
BFS
来解决多源最短路问题
需要满足边权为一
的条件，很明显这道题是符合的，所以按照下面的两步走：
- 将所有的源点加入到队列中
- 一层一层的往外拓展
但是有一个问题，如果我们按照题目的要求，以值为
1
的元素作为源点的话，会有一个问题，就是当所有的
1
作为源点去向外拓展找到
0
的时候，对于这个 “超级源点” 来说，只知道它本身距离
0
的长度，而并不知道里面每个
1
元素距离
0
的长度，这就麻烦了，如下图所示：
既然遇到这个问题，我们就换个思路，正难则反：
以值为
0
的元素作为源点向外拓展更新距离
！为什么这样子可以呢，因为以
0
作为源点的话，我们是知道
0
元素最后的距离其实就是
0
，而向外拓展每一层又可以更新
1
距离当前的距离，一举两得！
所以我们只需要
创建一个二维数组
distance
表示每个元素距离
0
元素的最近距离
，然后
将
0
位置的距离都初始化为
0
，而将
其它位置的距离都初始化为
-1
即可
，这样子后面我们也
不需要使用
used
数组
来标记走过的元素了，因为可以通过判断是否为
-1
来决定当前位置是否走过！如下图所示：
之后以
0
为源点向外一层一层的拓展，也就是将
0
位置都入队列，然后进行
bfs
操作，然后下一层的距离就是当前层距离加一了。下图是向外拓展一层的情况：
然后以此类推直到队列中没有节点为止，如下图所示：（红色表示当前队列中的节点，蓝色表示新一层更新的距离）
有了大概的思路，其实代码也不难写，和单源路径其实差不多
class Solution {
private:
int dx[4] = { 0, 0, -1, 1 };
int dy[4] = { -1, 1, 0, 0 };
public:
vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
int m = mat.size(), n = mat[0].size();
vector<vector<int>> distance(m, vector<int>(n, -1)); // 初始化距离矩阵为-1
// 正难则反：将0的位置都入队列，并且将其距离设置为0
queue<pair<int, int>> bfs;
for(int i = 0; i < m; ++i)
{
for(int j = 0; j < n; ++j)
{
if(mat[i][j] == 0)
{
distance[i][j] = 0;
bfs.push({i, j});
}
}
}
while(!bfs.empty())
{
// 一层一层往外拓展，更新距离
int size = bfs.size();
while(size--)
{
auto [x, y] = bfs.front();
bfs.pop();
for(int i = 0; i < 4; ++i)
{
int newx = x + dx[i], newy = y + dy[i];
if(newx >= 0 && newy >= 0 && newx < m && newy < n && distance[newx][newy] == -1)
{
bfs.push({newx, newy});
distance[newx][newy] = distance[x][y] + 1; // 只需要在当前距离上加一即可
}
}
}
}
return distance;
}
};