【多源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;
}
};腾讯云开发者
