## 题目描述：

LeetCode 542. 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.

Example 1:
Input:

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

Output:

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

Example 2:
Input:

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

Output:

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

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. 给定矩阵元素个数不超过10,000
2. 给定矩阵中至少包含1个0元素
3. 相邻单元格是指上、下、左、右四个方向

## 解题思路：

```初始令step = 0，将matrix中所有1元素加入队列queue

令step = step + 1

遍历queue中的元素，记当前元素为p，坐标为(x, y)：

若p的相邻元素中包含0元素，则p的距离设为step，从queue中移除p

将上一步中移除的元素对应的matrix值设为0```

## Python代码：

``````class Solution(object):
def updateMatrix(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: List[List[int]]
"""
h, w = len(matrix), len(matrix[0])
ans = [[0] * w for x in range(h)]
queue = [(x, y) for x in range(h) for y in range(w) if matrix[x][y]]
step = 0
while queue:
step += 1
nqueue, mqueue = [], []
for x, y in queue:
zero = 0
for dx, dy in zip((1, 0, -1, 0), (0, 1, 0, -1)):
nx, ny = x + dx, y + dy
if 0 <= nx < h and 0 <= ny < w and matrix[nx][ny] == 0:
zero += 1
if zero:
ans[x][y] = step
mqueue.append((x, y))
else:
nqueue.append((x, y))
for x, y in mqueue:
matrix[x][y] = 0
queue = nqueue
return ans
``````

Pingbacks已关闭。