# 0542. 01 Matrix
###### tags: `Leetcode` `Medium` `Dynamic Programming` `BFS` `Two Pass`
Link: https://leetcode.com/problems/01-matrix/description/
## 思路
### DP $O(MN)$ $O(MN)$
Two pass
对于每个1 ```dp[i][j] = min(dp[i-1][j], dp[i+1][j], dp[i][j-1], dp[i][j+1])+1```
所以我们可以先iterate from left to right and from top to down
然后iterate第二次 from right to left and from down to top

一开始的想法是先建一个dp array 记录第一次iterate的结果
然后再建一个dp array 记录第二次iterate的结果
然后答案就是取每个位置的最小值
但其实这样是不对的 因为我们如果离1最近的0在它的右上角 就无法找到
(因为这样的方法只是在找左上和右下的最小值然后比较大小, 但是如果直接在第一轮的结果上面改的话, 右上角的0的dist会传到和这个i同一行, 然后再通过第二次iterate from right to left, 传到这个1)
### BFS $O(MN)$ $O(MN)$
从所有的0开始层序遍历
## Code
DP

class Solution {
    public int[][] updateMatrix(int[][] mat) {
        int m = mat.length, n = mat[0].length;
        int[][] dp = new int[m][n];
        for(int i=0; i<m; i++) Arrays.fill(dp[i], Integer.MAX_VALUE/2);
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(mat[i][j]==0){
                    dp[i][j] = 0;
                    continue;
                }
                if(i!=0) dp[i][j] = dp[i-1][j]+1;
                if(j!=0) dp[i][j] = Math.min(dp[i][j], dp[i][j-1]+1);
            }
        }
        for(int i=m-1; i>=0; i--){
            for(int j=n-1; j>=0; j--){
                if(mat[i][j]==0){
                    dp[i][j] = 0;
                    continue;
                }
                if(i!=m-1) dp[i][j] = Math.min(dp[i][j], dp[i+1][j]+1);
                if(j!=n-1) dp[i][j] = Math.min(dp[i][j], dp[i][j+1]+1);
            }
        }
        return dp;
    }
}

BFS

class Solution {
    public int[][] updateMatrix(int[][] mat) {
        int m = mat.length, n = mat[0].length;
        int[][] ans = new int[m][n];
        Queue<int[]> q = new LinkedList<>();
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(mat[i][j]==0){
                    q.add(new int[]{i,j});
                }
            }
        }
        int[][] dirs = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
        int d = 0;
        while(!q.isEmpty()){
            int size = q.size();
            for(int i=0; i<size; i++){
                int[] curr = q.poll();
                ans[curr[0]][curr[1]] = d;
                for(int[] dir:dirs){
                    int nextx = curr[0]+dir[0];
                    int nexty = curr[1]+dir[1];
                    if(nextx>=0 && nextx<m && nexty>=0 && nexty<n){
                        if(mat[nextx][nexty]==1){
                            q.add(new int[]{nextx, nexty});
                            mat[nextx][nexty]=0;
                        }
                    }
                }
            }
            d++;
        }
        return ans;
    }
}