---

題目鏈接：

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;  // 返回距離矩陣}
};