# Leetcode 542：01 矩阵 01 Matrix

### 题目：

Given a matrix consists of 0 and 1, find the distance of the nearest 0 for each cell.

The distance between two adjacent cells is 1.

```0 0 0
0 1 0
0 0 0
```

```0 0 0
0 1 0
0 0 0
```

```0 0 0
0 1 0
1 1 1
```

```0 0 0
0 1 0
1 2 1
```

1. 给定矩阵的元素个数不超过 10000。
2. 给定矩阵中至少有一个元素是 0。
3. 矩阵中的元素只在四个方向上相邻: 上、下、左、右。

Note:

1. The number of elements of the given matrix will not exceed 10,000.
2. There are at least one 0 in the given matrix.
3. The cells are adjacent in only four directions: up, down, left and right.

### 解题思路：

```输入：
1 1 1
0 1 0
0 0 0
```

• 以节点1为根节点，求该节点到节点0之间的深度
• 以节点0为根节点，遇到最近的节点1路径计为1，再次以记录为1的节点为根节点继续向内遍历，遇到原节点1再次累加1并得到路径2，以此类推。。。

### 以0为根节点：

```1 1 1
0 1 1
0 0 1
```

……

Java：

```class Solution {

public int[][] updateMatrix(int[][] matrix) {
int row = matrix.length, column = matrix[0].length;
int[][] neighbors = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};//邻居节点的索引偏移量
for (int i = 0; i < row; i++) {
for (int j = 0; j < column; j++) {
if (matrix[i][j] == 0) queue.offer(new int[]{i, j});
else matrix[i][j] = Integer.MAX_VALUE;//节点值为1的节点改为一个路径不可能达到的值
}
}
while (!queue.isEmpty()) {
int[] tmp = queue.poll();
for (int i = 0; i < 4; i++) {
//得到邻居节点索引
int x = tmp[0] + neighbors[i][0];
int y = tmp[1] + neighbors[i][1];
if (x >= 0 && x < row && y >= 0 && y < column && matrix[tmp[0]][tmp[1]] < matrix[x][y]) {
matrix[x][y] = matrix[tmp[0]][tmp[1]] + 1;//该节点的值得到邻居节点的路径值+1
queue.offer(new int[]{x, y});
}
}
}
return matrix;
}
}
```

Python3：

```class Solution:
def updateMatrix(self, matrix: List[List[int]]) -> List[List[int]]:
row, column = len(matrix), len(matrix[0])
nerghbors = [(0, 1), (0, -1), (1, 0), (-1, 0)]
queue = collections.deque()
for i in range(row):
for j in range(column):
if matrix[i][j] == 0:
queue.append((i, j))
else:
matrix[i][j] = 10001

while queue:
x, y = queue.popleft()
for i, j in nerghbors:
xx = i + x
yy = j + y
if 0 <= xx < row and 0 <= yy < column and matrix[x][y] < matrix[xx][yy]:
matrix[xx][yy] = matrix[x][y] + 1
queue.append((xx, yy))

return matrix
```

### 以1为根节点：

Java：

```class Solution {
public int[][] updateMatrix(int[][] matrix) {
int row = matrix.length, column = matrix[0].length;
for (int i = 0; i < row; i++)
for (int j = 0; j < column; j++)
if (matrix[i][j] == 1) matrix[i][j] = bfs(matrix, i, j, row, column);
return matrix;
}

private int bfs(int[][] matrix, int i, int j, int row, int column) {
int count = 0;
Set<int[]> set = new HashSet<>();
while (!queue.isEmpty()) {
int size = queue.size();
count += 1;
for (int k = 0; k < size; k++) {
int tmp = queue.poll();
int x = tmp / column, y = tmp % column;//得到索引坐标
//处理上下左右四个邻居节点，遇到0节点直接返回count路径值
if (x + 1 < row && !set.contains((x + 1) * column + y)) {
if (matrix[x + 1][y] != 0) queue.add((x + 1) * column + y);
else return count;
}
if (x - 1 >= 0 && !set.contains((x - 1) * column + y)) {
if (matrix[x - 1][y] != 0) queue.add((x - 1) * column + y);
else return count;
}
if (y + 1 < column && !set.contains(x * column + y + 1)) {
if (matrix[x][y + 1] != 0) queue.add(x * column + y + 1);
else return count;
}
if (y - 1 >= 0 && !set.contains(x * column + y - 1)) {
if (matrix[x][y - 1] != 0) queue.add(x * column + y - 1);
else return count;
}
}
}
return count;
}
}
```

Python3：

```class Solution:
def updateMatrix(self, matrix: List[List[int]]) -> List[List[int]]:
row, column = len(matrix), len(matrix[0])
for i in range(row):
for j in range(column):
if matrix[i][j] == 1:
matrix[i][j] = self.bfs(i, j, matrix, row, column)

return matrix

def bfs(self, i: int, j: int, matrix: List[List[int]], row: int, column: int) -> int:
queue = collections.deque()
count = 0
nodeset = set()
queue.append((i, j))
while queue:
size = len(queue)
count += 1
for i in range(size):
x, y = queue.popleft()
if x + 1 < row and (x + 1, y) not in nodeset:
if matrix[x + 1][y] != 0:
queue.append((x + 1, y))
else:
return count
if x - 1 >= 0 and (x - 1, y) not in nodeset:
if matrix[x - 1][y] != 0:
queue.append((x - 1, y))
else:
return count
if y + 1 < column and (x, y + 1) not in nodeset:
if matrix[x][y + 1] != 0:
queue.append((x, y + 1))
else:
return count
if y - 1 >= 0 and (x, y - 1) not in nodeset:
if matrix[x][y - 1] != 0:
queue.append((x, y - 1))
else:
return count
return count
```

0 条评论

• ### Leetcode 498：对角线遍历Diagonal Traverse（python3、java）

给定一个含有 M x N 个元素的矩阵（M 行，N 列），请以对角线遍历的顺序返回这个矩阵中的所有元素，对角线遍历如下图所示。

• ### Leetcode 54:Spiral Matrix 螺旋矩阵

Given a matrix of m x n elements (m rows, n columns), return all elements of the...

• ### leetcode ​# 54:Spiral Matrix 螺旋矩阵

Given a matrix of m x n elements (m rows, n columns), return all elements of the...

• ### Leetcode 221. Maximal Square

Given a 2D binary matrix filled with 0's and 1's, find the largest square conta...

• ### Leetcode 48 Rotate Image

You are given an n x n 2D matrix representing an image. Rotate the image by 90...

• ### Leetcode-48-Rotate-Image

这个乍一看觉得不难，但是写的时候又不知道怎么回事，其实旋转，对于我们写程序来说，其实就是不停的调换位置，但是怎么调换是个问题。

• ### 【每日算法Day 93】不用额外空间，你会旋转一个矩阵吗？

给你一幅由 N × N 矩阵表示的图像，其中每个像素的大小为 4 字节。请你设计一种算法，将图像旋转 90 度。

• ### 【一天一大 lee】旋转图像 (难度:中等) - Day20201219

你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。

• ### Q221 Maximal Square

Given a 2D binary matrix filled with 0's and 1's, find the largest square contai...

• ### Array - 48. Rotate Image

You are given an n x n 2D matrix representing an image.