多源最短路徑

01矩陣

給定一個由 0 和 1 組成的矩陣 mat ，請輸出一個大小相同的矩陣，其中每一個格子是 mat 中對應位置元素到最近的 0 的距離。

兩個相鄰元素間的距離為 1

最短路徑 采用廣度優先搜尋BFS。如果采用周遊每一個 1，然後進行廣度優先搜尋，時間複雜度過大。這不是單源最短路問題。

是以采用從所有0開始搜尋，像廣播一樣。

多源廣度優先搜尋 可以添加 超級源點轉化為我們平時熟悉的單源 廣度優先搜尋。

1. 從超級源點出發
2. 同時到達矩陣中所有的0

3. 從所有的0開始向上下左右四個鄰居擴充。

   其實多源廣度優先搜尋就相當于單源廣度優先搜尋的第二步。

首先

初始化一個新的矩陣mat2，周遊mat矩陣，若為0，mat2相應的位置置為0，同時入隊列queue。（入隊列的為位置下标）若為1，mat2相應的位置置為max。

queue = []
mat2 = []
for i in range(len(mat)):
	mat2.append([])
    for j in range(len(mat[i])):
        if mat[i][j] == 0:
             mat2[i].append(0)
             queue.append((i,j))
        else:
             mat2[i].append(100000)
             
           

然後

就和單源廣度優先搜尋一樣進行周遊

oris = ((0,-1),(0,1),(-1,0),(1,0))
while len(queue)>0:
	r,c = queue[0];queue.pop(0)
    for ori in oris:
		new_r = r+ori[0];new_c = c+ori[1]
		if new_c>=0 and new_c<len(mat[0]) and new_r>=0 and new_r<len(mat):
			if mat2[new_r][new_c] > mat2[r][c]+1:
				mat2[new_r][new_c] = mat2[r][c]+1
				queue.append((new_r,new_c))
           

每次出隊一個元素（mat2[r][c]），如果其上下左右四個方向的某一方向（mat2[new_r][new_c]）的元素 比該出隊的元素加1 大，則這一方向的元素指派為 mat2[r][c]+1。并入隊。

完整代碼為：

class Solution:
    def updateMatrix(self, mat: list[list[int]]) -> list[list[int]]:
        queue = []
        mat2 = []
        for i in range(len(mat)):
            mat2.append([])
            for j in range(len(mat[i])):
                if mat[i][j] == 0:
                    mat2[i].append(0)
                    queue.append((i,j))
                else:
                    mat2[i].append(100000)

        oris = ((0,-1),(0,1),(-1,0),(1,0))
        while len(queue)>0:
            r,c = queue[0];queue.pop(0)
            for ori in oris:
                new_r = r+ori[0];new_c = c+ori[1]
                if new_c>=0 and new_c<len(mat[0]) and new_r>=0 and new_r<len(mat):
                    # print(f"new_r:{new_r},new_c:{new_c}")
                    if mat2[new_r][new_c] > mat2[r][c]+1:
                        mat2[new_r][new_c] = mat2[r][c]+1
                        queue.append((new_r,new_c))

        return mat2