# #0542. 01 矩阵open in new window

• 标签：广度优先搜索、数组、动态规划、矩阵
• 难度：中等

## # 题目大意

• 两个相邻元素间的距离为 $1$
• $m == mat.length$
• $n == mat[i].length$
• $1 \le m, n \le 10^4$
• $1 \le m * n \le 10^4$
• $mat[i][j] === 0$ 或者 $mat[i][j] == 1$
• $mat$ 中至少有一个 $0$

• 示例 1：
输入：mat = [[0,0,0],[0,1,0],[0,0,0]]


• 示例 2：
输入：mat = [[0,0,0],[0,1,0],[1,1,1]]



## # 解题思路

### # 思路 1：广度优先搜索

1. 使用一个集合变量 visited 存储所有值为 0 的元素坐标。使用队列变量 queue 存储所有值为 0 的元素坐标。使用二维数组 res 存储对应位置元素（即 $mat[i][j]$）到最近的 $0$ 的距离。
2. 我们从所有为如果队列 queue 不为空，则从队列中依次取出值为 0 的元素坐标，遍历其上、下、左、右位置。
3. 如果相邻区域未被访问过（说明遇到了值为 1 的元素），则更新相邻位置的距离值，并把相邻位置坐标加入队列 queue 和访问集合 visited 中。
4. 继续执行 2 ~ 3 步，直到队列为空时，返回 res

### # 思路 1：代码

import collections

class Solution:
def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
rows, cols = len(mat), len(mat)
res = [[0 for _ in range(cols)] for _ in range(rows)]
visited = set()

for i in range(rows):
for j in range(cols):
if mat[i][j] == 0:

directions = {(1, 0), (-1, 0), (0, 1), (0, -1)}
queue = collections.deque(visited)

while queue:
i, j = queue.popleft()
for direction in directions:
new_i = i + direction
new_j = j + direction
if 0 <= new_i < rows and 0 <= new_j < cols and (new_i, new_j) not in visited:
res[new_i][new_j] = res[i][j] + 1
queue.append((new_i, new_j))

• 时间复杂度$O(m \times n)$
• 空间复杂度$O(m \times n)$
{"ft_lang_label":"__label__zh","ft_lang_prob":0.8873147,"math_prob":0.999329,"size":1703,"snap":"2023-40-2023-50","text_gpt3_token_len":1141,"char_repetition_ratio":0.11359623,"word_repetition_ratio":0.024691358,"special_character_ratio":0.38990018,"punctuation_ratio":0.17027026,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9975256,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2023-12-08T10:38:24Z\",\"WARC-Record-ID\":\"<urn:uuid:1028962f-dcdf-4ddd-b054-27ddd9fba0ee>\",\"Content-Length\":\"208183\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:7cd65ecb-b8aa-4e9c-a037-03df9764d21d>\",\"WARC-Concurrent-To\":\"<urn:uuid:2b27bc30-4c78-4a38-aa0a-15fca37b4f4c>\",\"WARC-IP-Address\":\"81.70.100.28\",\"WARC-Target-URI\":\"https://algo.itcharge.cn/Solutions/0500-0599/01-matrix/\",\"WARC-Payload-Digest\":\"sha1:6MTUQJEOKYFVOP644JJOCPLDLMPSBRWK\",\"WARC-Block-Digest\":\"sha1:VDXJHYUWAMYBCHQAFGYHI3IJ255SUSVF\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2023/CC-MAIN-2023-50/CC-MAIN-2023-50_segments_1700679100739.50_warc_CC-MAIN-20231208081124-20231208111124-00361.warc.gz\"}"}