###### tags: `LeetCode` `Medium` `Queue` `BFS`
# LeetCode #542 [01 Matrix](https://leetcode.com/problems/01-matrix/)
### (Medium)

給定一個由 0 和 1 組成的矩陣 mat ，請輸出一個大小相同的矩陣，其中每一個格子是 mat 中對應位置元素到最近的 0 的距離。

兩個相鄰元素間的距離為 1 。

---
先建立一二維數組儲存矩陣元素對應的與0的距離, 初始值(0:0, 非0:-1)。
將所有值為0的座標點存入佇列中, 並以這些座標點進行往外DFS, 若遇到的座標點的值不是-1, 則要嘛是0, 要嘛是之前已經被探索過的節點(而由於BFS特性, 必定為與0節點的最短距離)。 將遇到的座標值為-1的座標存入佇列中, 並修改該座標的值為現在節點的距離值+1, 如此重複直到遇到的座標點皆不為-1, 此時換下一個佇列元素進行探索。

注意邊界條件。

---

class Solution {
public:
    vector<vector<int>> dir{{-1,0},{0,1},{1,0},{0,-1}};
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
        queue<pair<int,int>> q;
        int m = mat.size();
        int n = mat[0].size();
        vector<vector<int>> ans(m, vector<int>(n, -1));
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(mat[i][j]==0){
                    ans[i][j]=0;
                    q.push({i,j});
                }
            }
        }
        while(!q.empty()){
            for(int i=q.size();i>0;i--){
                pair<int,int> p = q.front();q.pop();
                for(auto& x:dir){
                    int a=p.first+x[0];
                    int b=p.second+x[1];
                    if(isvalid(a,b,m,n)&&ans[a][b]==-1){
                        q.push({a,b});
                        ans[a][b]=ans[p.first][p.second]+1;
                    }
                }
            }
        }
        return ans;
    }
    bool isvalid(int i, int j, int m, int n){
        if(i==m||j==n||i<0||j<0)return false;
        return true;
    }
};