> For the complete documentation index, see [llms.txt](https://junnie.gitbook.io/nine-chapter/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://junnie.gitbook.io/nine-chapter/3.breadth-first-search/542.-01-matrix-m.md).

# 542. 01 Matrix (M)

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

 

**Example 1:**

![](https://assets.leetcode.com/uploads/2021/04/24/01-1-grid.jpg)

```
Input: mat = [[0,0,0],[0,1,0],[0,0,0]]
Output: [[0,0,0],[0,1,0],[0,0,0]]
```

**Example 2:**

![](https://assets.leetcode.com/uploads/2021/04/24/01-2-grid.jpg)

```
Input: mat = [[0,0,0],[0,1,0],[1,1,1]]
Output: [[0,0,0],[0,1,0],[1,2,1]]
```

 

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

### Solution:

<https://www.jiuzhang.com/problem/01-matrix/>

**Version 1: BFS**

先把所有的0 进queue， 再一个一个pop

```
class Solution {
    private int[][] result;
    public int[][] updateMatrix(int[][] mat) {
        
        int m = mat.length;
        int n = mat[0].length;
        int[][] result = new int[m][n];
        boolean[][] visited = new boolean[m][n];
        Queue<Node> queue = new LinkedList<Node>();
        
        int[] dx = new int[]{-1,1,0,0};
        int[] dy = new int[]{0,0,-1,1};
        for(int i = 0; i< m; i++)
        {
            for(int j = 0; j< n; j++)
            {
                if(mat[i][j] == 0)
                {
                    visited[i][j] = true;
                    queue.offer(new Node(i,j));
                    
                    result[i][j] = 0;
                }else
                {
                    result[i][j] = Integer.MAX_VALUE;
                }
            }
        }
        
        while(! queue.isEmpty())
        {
            int size = queue.size();
            for(int i = 0;i< size;i++)
            {
                Node current = queue.poll();
                for(int k = 0; k< 4; k++)
                {
                    int directX = current.x + dx[k];
                    int directY = current.y + dy[k];
                    if(isBound(mat, directX, directY) && !visited[directX][directY])
                    {
                        queue.offer(new Node(directX, directY));
                        visited[directX][directY] = true;
                        result[directX][directY] = Math.min(result[directX][directY], result[current.x][current.y] + 1);
                    }
                }
            }
        }
        return result;
    }
    
    
    public boolean isBound(int[][] mat, int x, int y)
    {
        int m = mat.length;
        int n = mat[0].length;
        return x>=0 & x<m && y >=0 && y<n;
    }
}

class Node
{
    int x;
    int y;
    Node(int x, int y)
    {
        this.x = x;
        this.y = y;
        
    }
}
```

**Version 2: DP**

从左上出发推一遍。 从右下出发推一遍。

```
public class Solution {
    /**
     * @param matrix: a 0-1 matrix
     * @return: return a matrix
     */
    public int[][] updateMatrix(int[][] matrix) {
        // write your code here
        int n = matrix.length, m = matrix[0].length;
        int[][] dp = new int[n][m];
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (matrix[i][j] == 0) dp[i][j] = 0;
                //注意这里不要给MAX_VALUE不要会溢出。test case 见下
                else dp[i][j] = 1000000;
                if (i > 0) dp[i][j] = Math.min(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 = n - 1; i >= 0; --i) {
            for (int j = m - 1; j >= 0; --j) {
                if (dp[i][j] > 0) {
                    if (i < n - 1) dp[i][j] = Math.min(dp[i][j], dp[i + 1][j] + 1);
                    if (j < m - 1) dp[i][j] = Math.min(dp[i][j], dp[i][j + 1] + 1);
                }
            }
        }
        return dp;
    }
}
```

test case:

Input: \[\[1,0,1,1,0,0,1,0,0,1],\[0,1,1,0,1,0,1,0,1,1],\[0,0,1,0,1,0,0,1,0,0],\[1,0,1,0,1,1,1,1,1,1],\[0,1,0,1,1,0,0,0,0,1],\[0,0,1,0,1,1,1,0,1,0],\[0,1,0,1,0,1,0,0,1,1],\[1,0,0,0,1,1,1,1,0,1],\[1,1,1,1,1,1,1,0,1,0],\[1,1,1,1,0,1,0,0,1,1]]&#x20;

Output: \[\[-2147483647,-2147483648,-2147483647,-2147483646,-2147483645,-2147483644,-2147483643,-2147483642,-2147483641,-2147483640],\[-2147483648,-2147483647,-2147483646,-2147483645,-2147483644,-2147483643,-2147483642,-2147483641,-2147483640,-2147483639],\[-2147483647,-2147483646,-2147483645,-2147483644,-2147483643,-2147483642,-2147483641,-2147483640,-2147483639,-2147483638],\[-2147483646,-2147483645,-2147483644,-2147483643,-2147483642,-2147483641,-2147483640,-2147483639,-2147483638,-2147483637],\[-2147483645,-2147483644,-2147483643,-2147483642,-2147483641,-2147483640,-2147483639,-2147483638,-2147483637,-2147483636],\[-2147483644,-2147483643,-2147483642,-2147483641,-2147483640,-2147483639,-2147483638,-2147483637,-2147483636,-2147483635],\[-2147483643,-2147483642,-2147483641,-2147483640,-2147483639,-2147483638,-2147483637,-2147483636,-2147483635,-2147483634],\[-2147483642,-2147483641,-2147483640,-2147483639,-2147483638,-2147483637,-2147483636,-2147483635,-2147483634,-2147483633],\[-2147483641,-2147483640,-2147483639,-2147483638,-2147483637,-2147483636,-2147483635,-2147483634,-2147483633,-2147483632],\[-2147483640,-2147483639,-2147483638,-2147483637,-2147483636,-2147483635,-2147483634,-2147483633,-2147483632,-2147483631]]&#x20;

Expected: \[\[1,0,1,1,0,0,1,0,0,1],\[0,1,1,0,1,0,1,0,1,1],\[0,0,1,0,1,0,0,1,0,0],\[1,0,1,0,1,1,1,1,1,1],\[0,1,0,1,1,0,0,0,0,1],\[0,0,1,0,1,1,1,0,1,0],\[0,1,0,1,0,1,0,0,1,1],\[1,0,0,0,1,2,1,1,0,1],\[2,1,1,1,1,2,1,0,1,0],\[3,2,2,1,0,1,0,0,1,1]]