---
# System prepended metadata

title: 542. 01 Matrix
tags: [Graphs - BFS, medium, Grind 75, important]

---

思考:
判斷要用BFS還是DFS，通常找最短距離都是用BFS，掃描全部的點才DFS
從 0 的點位開始 BFS 所有的點(上下左右)
初始設定非 0 的距離都是最大值 (n * m)
1. 從 0 的點位開始上下左右 BFS 如果出現比這個點位 +1 大的值(代表要更新距離)就設為 初始點位 +1 並且放入queue中等待BFS


```c++=
class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
       int m = mat.size();
       int n = mat[0].size(); 
       //存放 0 的點位 
       queue<pair<int, int>> q;
       for(int i = 0; i < m; i++){
           for(int j = 0; j < n; j++){
               if(mat[i][j] == 0){
                   q.push({i, j});
               }else{
                   //如果非零就先設定為最大值
                   mat[i][j] = m * n;
               }
           }
       }
       // 右 左 下 上
        vector<pair<int, int>> dir = {{0,1}, {0, -1}, {1, 0}, {-1, 0}};
        // BFS
        while(!q.empty()){
            int row = q.front().first;
            int col = q.front().second;
            q.pop();
            for(auto i : dir){
                int r = row + i.first;
                int c = col + i.second;
                if(r >= 0 && r < m && c >= 0 && c < n && mat[r][c] > mat[row][col] + 1){
                    q.push({r, c});
                    mat[r][c] = mat[row][col] + 1;
                }
            }
        }


        return mat;
    }
};

```