# 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]]


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://junnie.gitbook.io/nine-chapter/3.breadth-first-search/542.-01-matrix-m.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.