# [LeetCode 542. 01 Matrix ]()
### Daily challenge Jul 29, 2021 (MEDIAN)

>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`.


:::info
**Example 1:**
**Input:** mat = [[0,0,0],[0,1,0],[0,0,0]]
**Output:** [[0,0,0],[0,1,0],[0,0,0]]
:::


:::info
**Example 2:**
**Input:** mat = [[0,0,0],[0,1,0],[1,1,1]]
**Output:** [[0,0,0],[0,1,0],[1,2,1]]
:::

:::warning
**Constraints:**
* m == mat.length
* n == mat[i].length
* 1 <= m, n <= 104
* 1 <= m * n <= 104
* mat[i][j] is either 0 or 1.
* There is at least one 0 in mat.
:::

---

### Approach 1 : BFS :bulb:
**`132 ms ( 22.09% )`** **`O()`**

:::success
使用 `1` 去搜尋最近的 `0`。
速度較慢且浪費空間，出現很多的多餘計算 :x:。
:::

* 使用 `ans` 紀錄距離。
> 1. `mat[i][j] == 0`，距離為 0 ---> `ans[i][j] = 0`。
> 2. `mat[i][j] == 1` ---> 使用 **`BFS`** 尋找最近的 `0`。

* BFS :
> 1. `dir` 紀錄走的方向、`used` 紀錄走過的位置、`step` 紀錄步數。
> 2. 判斷 `next_x`、`next_y`。
>> * 若不在 `mat` 範圍內 ---> 不必判斷。
>> * 若 **`mat[next_x][next_y] == 0`** ---> **找到答案**，並回傳 `step`。
>> * 若沒有走過 ---> `push` 到 `queue` 中，並記錄位置。

class Solution {
public:
    int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    
    int BFS(pair<int, int> one, vector<vector<int>>& mat){
        int m = mat.size();
        int n = mat[0].size(); 
        bool used[m][n];
        memset(used, false, sizeof(used));
        
        queue<pair<int, int>> bfs;
        bfs.push(one);
        
        int step = 1;
        while(bfs.size() != 0){
            for(int i=bfs.size()-1; i>=0; i--){
                auto now = bfs.front();
                bfs.pop();
                
                for(auto DIR : dir){
                    int next_x = now.first + DIR[0];
                    int next_y = now.second + DIR[1];
                    
                    if(next_x < 0 || next_x >= m || next_y < 0 || next_y >= n)  continue;
                    if(mat[next_x][next_y] == 0)  return step;
                    if(!used[next_x][next_y]){
                        used[next_x][next_y] = true;
                        bfs.push({next_x, next_y});
                    }
                }
            }
            
            step++;
        }
        
        return -1;
    }
    
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
        int m = mat.size();
        int n = mat[0].size();
        
        vector<vector<int>> ans(m, vector<int>(n, 0));
        for(int i=0; i < m; i++){
            for(int j=0; j < n; j++){
                if(mat[i][j] == 1)  ans[i][j] = BFS({i, j}, mat);
            }
        }
        
        return ans;
    }
};

### Approach 2 : BFS :book:
**`68 ms ( 72.39% )`** **`O()`**

:::success
使用 `0` 去搜尋附近的 `1` :o:。
整體與 `Approach 1` 想法相同。
:::

與 `Approach 1` 不同的地方 :
* 將 `mat[i][j] == 1` 的部分先設為 `INT_MAX`。
`mat[i][j] == 0` 的部分存入 `queue` 中。
* BFS :
> 同樣判斷 `next_x`、`next_y`。
>> 1. `mat[next_x][next_y] == 0` ---> 不必判斷，因為只會增加步數。
>> 2. `mat[next_x][next_y] == 1`
>> ---> 判斷當前 `ans[next_x][next_y]` 以及 `ans[x][y] + 1` 大小。
>> ---> 若 `ans[next_x][next_y] > ans[x][y] + 1`，表示從當前的`{ x, y }` 走到
>> `{ next_x, next_y }` 會有較近的距離。
>> ---> 若 `ans[next_x][next_y] <= ans[x][y] + 1`，則表示之前所記錄走到
>> `{ next_x, next_y }` 已經是較好的結果。

class Solution {
public:
    int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
        int m = mat.size();
        int n = mat[0].size();
        
        queue<pair<int, int>> bfs;
        vector<vector<int>> ans(m, vector<int>(n, INT_MAX));
        for(int i=0; i < m; i++){
            for(int j=0; j < n; j++){
                if(mat[i][j] == 0){
                    bfs.push({i, j});
                    ans[i][j] = 0;
                }
            }
        }
        
        while(!bfs.empty()){
            for(int i=bfs.size()-1; i>=0; i--){
                pair<int, int> now = bfs.front();
                bfs.pop();
                
                for(auto DIR : dir){
                    int next_x = now.first + DIR[0];
                    int next_y = now.second + DIR[1];
                    
                    if(next_x < 0 || next_x >= m || next_y < 0 || next_y >= n
                      || ans[next_x][next_y] <= ans[now.first][now.second] + 1)  continue;
                    
                    bfs.push({next_x, next_y});
                    ans[next_x][next_y] = ans[now.first][now.second] + 1;
                }
            }
        }
        
        return ans;
    }
};