###### tags: `Leetcode` `medium` `array` `bfs` `python` `c++`

# 542. 01 Matrix

## [題目連結:] https://leetcode.com/problems/01-matrix/description/

## 題目:
Given an ```m x n``` binary matrix ```mat```, return the distance of the nearest ```0``` for each cell.

The distance between two adjacent cells is ```1```.


## 解題想法:
* 此題為給一個只有0與1個矩陣，求每個1到與其最近的0的距離
* 使用BFS尋找更新
* 初始:
* 創建一個同mat大小的matrix res
* 初始皆為float('inf')
* BFS需要的queue: que
* dirs=[(1,0), (-1,0), (0,1), (0,-1)]: 紀錄四個方位
* **Step1**: 對於matrix[i][j]==0的位置(i,j)
* res[i][j]=0
* que.append((i,j))
* **Step2**: while que
* 每次pop獲取當前位置
* curx,cury
* 對於周圍四個鄰居 tmpx,tmpy
* 若符合在界內且於matrix值為1
* 判斷是否res[tmpx][tmpy]>res[curx][cury]+1
* 若符合，則更新res值並將(tmpx,tmpy)加入que

## Python:

class Solution(object):
    def updateMatrix(self, mat):
        """
        :type mat: List[List[int]]
        :rtype: List[List[int]]
        """
        m=len(mat)
        n=len(mat[0])
        res=[ [ float('inf') for _ in range(n)] for _ in range(m)]
        que=[]
        #初始 若本身該格為0 距離依然為0
        for i in range(m):
            for j in range(n):
                if mat[i][j]==0:
                    res[i][j]=0
                    que.append((i,j))
        dirs=[(1,0), (-1,0), (0,1), (0,-1)]
        #bfs
        #從0的位置去更新1
        while que:
            curx, cury=que.pop(0)
            for dirx, diry in dirs:
                tmpx=curx+dirx
                tmpy=cury+diry
                #判斷是否出界
                if 0<=tmpx<m and 0<=tmpy<n and mat[tmpx][tmpy]==1:
                    #更新res
                    if res[tmpx][tmpy]>res[curx][cury]+1:
                        res[tmpx][tmpy]=res[curx][cury]+1
                        que.append((tmpx, tmpy))
        return res

mat = [[0,0,0],[0,1,0],[1,1,1]]
result=Solution()
ans=result.updateMatrix(mat)
print(ans)

## C++:

class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
        int m=mat.size();
        int n=mat[0].size();
        vector<vector<int>> res(m, vector<int>(n, INT_MAX));
        vector<pair<int, int>> dirs={ {1,0}, {-1,0}, {0,1}, {0,-1}};
        queue<pair<int, int>> que;
        //init the res, add (i,j) to que
        for (int i=0; i<m; i++){
            for (int j=0; j<n; j++){
                if (mat[i][j]==0){
                    res[i][j]=0;
                    que.push(make_pair(i,j));
                }
            }
        }
        while (!que.empty()){
            pair<int,int> cur=que.front(); que.pop();
            int curx=cur.first, cury=cur.second;
            //check neighber
            for (auto dir: dirs){
                int tmpx=curx+dir.first;
                int tmpy=cury+dir.second;
                //out of range or illegal
                if (tmpx<0 || tmpx>=m || tmpy<0 || tmpy>=n || mat[tmpx][tmpy]==0)
                    continue;
                if (res[tmpx][tmpy]>res[curx][cury]+1){
                    res[tmpx][tmpy]=res[curx][cury]+1;
                    que.push(make_pair(tmpx, tmpy));
                }
            }
        }
        return res;
    }
};