---

题目链接：

542. 01 矩阵

---

题目描述：

---

解法

先看懂题目

解法一：一个位置一个位置求（最差的情况下会非常恐怖）

解法二：多源BFS+正难则反

把1当成起点就很难，因为不好更新。

所以把0当作起点，1当作终点，从0开始向外扩展，遇到1就把最短路数填进去。

1. 把所有的0位置加入到队列中
2. 一层一层的向外扩展即可

---

C++ 算法代码：

class Solution {// 四个方向的移动：右、左、下、上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();// 初始化距离矩阵// dist[i][j] == -1 表示该位置还未被访问// dist[i][j] != -1 表示该位置到最近0的距离vector<vector<int>> dist(m, vector<int>(n, -1));queue<pair<int, int>> q;// 1. 多源BFS初始化：将所有0的位置作为起点for (int i = 0; i < m; i++)for (int j = 0; j < n; j++)if (mat[i][j] == 0) {q.push({i, j});dist[i][j] = 0;  // 0到自己的距离是0}// 2. 开始BFS遍历while (q.size()) {auto [a, b] = q.front();q.pop();// 遍历四个方向for (int i = 0; i < 4; i++) {int x = a + dx[i], y = b + dy[i];// 检查新位置是否在矩阵范围内且未被访问过if (x >= 0 && x < m && y >= 0 && y < n && dist[x][y] == -1) {// 更新距离：当前点的距离 = 前一个点的距离 + 1dist[x][y] = dist[a][b] + 1;// 将新位置加入队列，继续BFSq.push({x, y});}}}return dist;  // 返回距离矩阵}
};