[leet1765] Multi-source BFS. 重複しない部分のみを参照

Multi-source BFS

BFSとDFSの区別と定義は再帰DFSに関する問題である.つまり、[link]の同じレベルのノードにアクセスしてから、次のレベルに進みます.
この問題のように、ますます「拡散」する問題では、コードは簡単なDFSアクセスではなくBFSアクセスを使用すべきであり、特にマルチソースアクセスを使用する考えが必要である.
次の図のように、数字が一つ一つ増え、一つ一つ広がっていく場合を考えてみましょう.BFSを使ってナビゲーションを行う場合、ルートごとに1つの格しか分散できず、次のレベルに入るので、ある2つの点から出発すると、真ん中で出会うことになります.自然に隣接する格子が一番です.空欄が必要な場合、A点付近の点のみがA点のナビゲーションで生成されます.次の問題を見ると理解に役立ちます.

# multi-source BFS
queue = deque([root1, root2, root3])
while queue:
	blah blah

Question

0は土地、1は水
新しいマトリクスを作成

水は0、土地は0または1、隣接する

春example 1
[[1, 0],
[0,0]の場合
[[1, 0],
[2,1]この土地の形

Solution

隣接(次のレベル)は1+1ずつ増加するので、BFSを使用して同じレベルからナビゲートを開始して、数値を割り当てる必要があります.

Solution 1. まず,各water点から出発するBFSをそれぞれ回転させ,それぞれ生成したheight mapを用いて各点から最小値を解答として選択する.
Solution 2. waterブランチを同じレベルとしてキューに入れ、BFSを起動します.各レベルごとに1つの数字の割り当てが行われ、最終的には水1と水2点の中間で出会い、差は1を超えない.
SOL 1に比べて探索が必要な場所が著しく減少し、通過時間の制限を超えない!!
PSEUDO sol 1:コードが長すぎます.下のgithubページのソリューション1を参照してください.

回答map(0からなる入力マトリクスと同じサイズのマトリクス)

def BFS:BFSの答えが0にマッピングされた場合、既存の高さと現在のBFSの高さとの間に小さなエッジが割り当てられ、0の場合、

の高さが割り当てられます.

すべての水源点でBFS

を起動する.

PSEUDO sol2

水支点は第1の列の中で

に並んでいる.

BFSをそのまま起動
答えmapに数字が割り当てられていない部分のみナビゲート&数字の割り当て
同じレベルで同じ順序で探索とデジタル割り当てが行われるため,2つの水点の同じ場所で探索に遭遇する.(よく理解するポイント!

def sol_2(isWater):
    r = len(isWater)
    c = len(isWater[0])
    newiswater = [[None for k in range(c)] for l in range(r)]
    deq = deque()

    for row in range(r):
        for col in range(c):
            if isWater[row][col] == 1:
                deq.append([row, col])
                newiswater[row][col] = 0

    while deq:
        row, col = deq.popleft()
        for new_row, new_col in [(row+1, col), (row-1, col), (row, col-1), (row, col+1)]:
            if 0 <= new_row < r and 0 <= new_col < c and newiswater[new_row][new_col] is None: # ()
                newiswater[new_row][new_col] = newiswater[row][col] + 1
                deq.append((new_row, new_col))
    return newiswater

github