48 lines
1.6 KiB
Markdown
48 lines
1.6 KiB
Markdown
---
|
||
title: leetcode-01-matrix
|
||
date: 2020-04-16 12:26:34
|
||
tags:
|
||
categories: leetcode
|
||
---
|
||
|
||
### 542. 01 矩阵
|
||
|
||
[题目](https://leetcode-cn.com/problems/01-matrix/)
|
||
|
||
|
||
|
||
<!--more-->
|
||
|
||
|
||
|
||
想了两种思路
|
||
|
||
1. 0 位置的上下左右是 1， 上下左右中有跟 1 相邻的就是 2，以此类推，从 0 的坐标开始往上下左右四个方向扩散。如果我们把同意个距离的看作是一层，可以用一个队列依次存放每一层的坐标，直至每个坐标都被计算过。
|
||
|
||
```python
|
||
class Solution:
|
||
def updateMatrix(self, matrix: List[List[int]]) -> List[List[int]]:
|
||
m, n = len(matrix), len(matrix[0])
|
||
dist = [[0] * n for _ in range(m)]
|
||
zeroes_pos = [(i, j) for i in range(m) for j in range(n) if matrix[i][j] == 0]
|
||
# 将所有的 0 添加进初始队列中
|
||
q = collections.deque(zeroes_pos)
|
||
seen = set(zeroes_pos)
|
||
|
||
# 广度优先搜索
|
||
while q:
|
||
i, j = q.popleft()
|
||
for ni, nj in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
|
||
if 0 <= ni < m and 0 <= nj < n and (ni, nj) not in seen:
|
||
dist[ni][nj] = dist[i][j] + 1
|
||
q.append((ni, nj))
|
||
seen.add((ni, nj))
|
||
|
||
return dist
|
||
```
|
||
|
||
|
||
|
||
2. 从左上角开往右下角遍历矩阵，当前坐标的距离由左和上两个位置的值确定。遍历一遍后，再反过来从右下角开始往左上角遍历，当前坐标的距离根据右和下两个位置的值确定，比较这两次得出的值中较小的一个即为该点的距离。
|
||
|