> For the complete documentation index, see [llms.txt](https://timmybeeflin.gitbook.io/cracking-leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://timmybeeflin.gitbook.io/cracking-leetcode/dfs-and-bfs/bfs/542.-01-matrix.md).

# 542. 01 Matrix

![](/files/-MeJaiffZOgbgH3bW8Ay)

![](/files/-MeJald5gqEgTC-Nc3fI)

![](/files/-MjKCXrHJSfxmM1Wlv-u)

## follow template style

time: O(mn)

space: O(mn)

```java
class Solution {
    private static final int DIRECTIONS[][] = {{0,1}, {1, 0}, {0, -1}, {-1,0}};

    public int[][] updateMatrix(int[][] mat) {
        // BFS from 0 to find 1, record dist in res, run all queue level++
        int m = mat.length, n = mat[0].length;
        int[][] res = new int[m][n];
        
        boolean vistited[][] = new boolean[m][n];
        Queue<int[]> queue = new LinkedList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (mat[i][j] == 0) {
                    queue.offer(new int[]{i, j}); // 00 01 02 10 12
                    vistited[i][j] = true;
                }
            }
        }
        int dist = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int q = 0; q < size; q++) {
                int cell[] = queue.poll();
                int i = cell[0];
                int j = cell[1];
                if (mat[i][j] == 1) {
                    res[i][j] = dist;
                }
                for (int dir[] : DIRECTIONS) {
                    int x = i + dir[0];
                    int y = j + dir[1];
                    if (x >= 0 && x < m && y >=0 && y < n && !vistited[x][y]) {
                        queue.offer(new int[]{x, y});
                        vistited[x][y] = true;
                    }
                }
            }
            dist++;
        }
        return res;
    }
}
```

## Use some tricks

use MAX to represent 1 and not visited, update 1's value to dist (but I think it's not different)

just save some space, time is the same

```java
class Solution {
    private static final int DIRECTIONS[][] = {{0,1}, {1, 0}, {0, -1}, {-1,0}};

    public int[][] updateMatrix(int[][] mat) {
        // BFS from 0 to find 1, put 0 into queue, 1 mark MAX, so when meet MAX, if new node (MAX) > prenode+1
        // update new node = prenode+1
        int m = mat.length, n = mat[0].length;

        Queue<int[]> queue = new LinkedList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (mat[i][j] == 0) {
                    queue.offer(new int[]{i, j}); // 00 01 02 10 12
                } else {
                    mat[i][j] = Integer.MAX_VALUE;
                }
            }
        }
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int q = 0; q < size; q++) {
                int cell[] = queue.poll();
                int i = cell[0];
                int j = cell[1];
                for (int dir[] : DIRECTIONS) {
                    int x = i + dir[0];
                    int y = j + dir[1];
                    if (x >= 0 && x < m && y >=0 && y < n && mat[x][y] > mat[i][j] + 1) {
                        queue.offer(new int[]{x, y});
                        mat[x][y] = mat[i][j] + 1;
                    }
                }
            }
        }
        return mat;
    }
}
```

## latest one:

```java
/**
use 0 as start, when find 1, we find the dist in "this BFS" (so it's O(mn))

but if we use 1 as start, when find 0 -> it's hard to fill answer in this BFS
-> become you have to run many times BFS to get dist
 */
```

```java
class Solution {
    private record Step(int x, int y, int level){};
    private static final int[][] DIRECTIONS = {{0,1}, {1,0}, {0,-1}, {-1,0}};
    
    public int[][] updateMatrix(int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;
        Queue<Step> queue = new LinkedList<>();
        boolean[][] visited = new boolean[m][n];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (mat[i][j] == 0) {
                    queue.offer(new Step(i, j, 0));
                }
            }
        }

        while (!queue.isEmpty()) {
            Step cur = queue.poll();
            if (cur.x < 0 || cur.x >= m || cur.y < 0 || cur.y >= n || visited[cur.x][cur.y]) {
                continue;
            }
    
            visited[cur.x][cur.y] = true;
            if (mat[cur.x][cur.y] == 1) {
                mat[cur.x][cur.y] = cur.level;
            }
            for (int[] dir : DIRECTIONS) {
                queue.offer(new Step(cur.x + dir[0], cur.y + dir[1], cur.level+1));
            }
        }
        return mat;
    }
}

/**

 */
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## 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, and the optional `goal` query parameter:

```
GET https://timmybeeflin.gitbook.io/cracking-leetcode/dfs-and-bfs/bfs/542.-01-matrix.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

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.