Swim in Rising Water
各行のリストとして、0 から n²-1 までのすべての数がそれぞれちょうど1回ずつ含まれる、高さの n × n グリッドが与えられます。時刻0に雨が降り始め、時刻 t には水位がどこでも高さ t になるため、高さが t 以下のすべてのマスが水に沈みます。左上のマスからスタートします。両方のマスが水に沈んでいるとき、辺を共有するマス同士を泳いで移動でき、泳ぐのに時間はかかりません。右下のマスに到達できる最も早い時刻を返してください。
関数
- gridinteger-2d-array
- 高さを、n 個の数値からなる n 行のリストとして
- 戻り値integer
- 右下のセルに到達できる最も早い時刻
制約
n == grid.length == grid[i].length1 ≤ n ≤ 1000 ≤ grid[i][j] ≤ n²-1- 0 から
n²-1までのすべての値が、それぞれちょうど1回ずつ現れます。
例
- 入力
- grid = [[0, 2], [3, 1]]
- 出力
- 2
- 説明
- 右上のセルを通る経路は 0, 2, 1 で、最も高いセルは 2 です。左下のセルを通る経路は 0, 3, 1 で、最も高いセルは 3 です。時刻 2 では最初の経路が水没しているため、答えは 2 です。
- 入力
- grid = [[0, 1, 2, 3, 4], [24, 23, 22, 21, 5], [12, 13, 14, 15, 16], [11, 17, 18, 19, 20], [10, 9, 8, 7, 6]]
- 出力
- 16
- 説明
- 時刻15では最上段と、その端の下にある5に到達できますが、そのエリアから出る経路はどれも16以上を通ります。右側をまっすぐ下ると16に到達し、その後20に進みます。16で左に曲がり、15、14、13、12、11を通って下段に沿って戻ると、16を超えることはないため、答えは16です。
- 入力
- grid = [[3, 0], [1, 2]]
- 出力
- 3
- 説明
- 開始セルの高さは3なので、時刻3になる前はそこにいることも、そこから出ることもできません。その時点では、グリッド全体が水没しています。
提出時に隠しテスト+13件
発展問題
高さが重複し、10^9に達する可能性がある場合、あなたのアプローチのうち、変更せずに機能するのはどれですか？また、何を対象に二分探索しますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
水位
tがわかっているとします。通り抜けられる道があるかどうか判断できますか？tが大きくなるにつれて、その答えはどのように変わりますか？経路上のすべてのマスを水が覆う必要があるため、経路に必要な時間は、その経路上で最も標高の高いマスによって決まります。両端の角を結ぶ経路のうち、最も高いマスの標高ができるだけ低い経路を見つけましょう。
テストとしてフラッドフィルを使って
tを二分探索するか、各セルの時刻を到着時刻とそのセル自身の高さの大きい方として、最小ヒープを使ってダイクストラ法を実行します。右下のセルがヒープから取り出されたら終了します。
解説
ルートに必要な時間は、そのルート上で最も高いセルによって決まります。通過するすべてのセルを水が覆う必要があるためです。したがって、目的は、最高地点ができるだけ低くなるような角どうしを結ぶルートを見つけることです。つまり、経路のコストが合計ではなく最大値となる最短経路です。水位を一段階ずつ上げてテストする方法、同じテストを使って水位を二分探索する方法、または最高地点をコストとしてダイクストラ法を実行する方法があります。
水位を一段ずつ上げる
正しいが、最大のテストでは終わらない
考え方
水位 t を固定します。到達できるマスは、高さが t 以下で、そのようなマスを通ってスタート地点につながっているマスです。左上から一度塗りつぶし探索を行えば、それらを見つけられます。スタート地点を追加し、マスを取り出して、高さが t 以下の未訪問の隣接マスをそれぞれ追加します。右下のマスが訪問済みになれば、水位 t で十分です。
答えは、塗りつぶし探索で到達できる最小の t です。両方の角が水面下にある必要があるため、答えは高い方の角の高さ max(grid[0][0], grid[n-1][n-1]) を下回ることはありません。そこから始めて、探索が成功するまで1ずつ増やします。水位が上がるとマスが新たに通れるようになることはあっても、通れなくなることはないため、最初に成功した水位が答えです。つまり、一度成功した水位では、その後も成功します。
各テストの計算量は O(n²) で、到達できるようになるまで水位がほぼ n² 回上がることがあります。100 × 100 のグリッドでは、水位の候補が最大で 10^4 個あり、それぞれで 10^4 個のマスを調べるため、訪問回数は約 10^8 回になります。大きなテストでは角の値が 0 と 1 で、答えは 4,950 から 9,998 の間にあるため、答えが見つかるまでに塗りつぶし探索を何千回も実行することになります。
アルゴリズム
tを2つの角の高さのうち高い方に設定します。- 明示的なスタックとセルごとの訪問済みマークを使い、高さが
t以下のセルを通って左上からフラッドフィルします。 - 塗りつぶしが右下に到達したら、
tを返します。 - それ以外の場合は、
tに1を加えて再度塗りつぶします。
def canReach(grid, t):
# True when you can swim from the top left to the bottom right with the water at height t.
n = len(grid)
seen = [[False] * n for _ in range(n)]
seen[0][0] = True
stack = [(0, 0)]
while stack:
r, c = stack.pop()
if r == n - 1 and c == n - 1:
return True
for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
if 0 <= nr < n and 0 <= nc < n and not seen[nr][nc] and grid[nr][nc] <= t:
seen[nr][nc] = True
stack.append((nr, nc))
return False
def swimInWater(grid):
n = len(grid)
# You cannot finish before the water covers both corners.
t = max(grid[0][0], grid[n - 1][n - 1])
# Raise the water one step at a time until a way through opens.
while not canReach(grid, t):
t += 1
return t水位に対する二分探索
考え方
最初の方法のテストは、便利な性質を持っています。答えより小さいすべての水位で失敗し、答え以上のすべての水位で成功します。答えが「いいえ」から「はい」へと一度だけ切り替わる質問を、二分探索は対数回の試行で見つけます。
lo（高い方の角）と、hi = n²-1（最も高いマス）の間を探索します。この水位ではグリッド全体が水没しており、テストは必ず成功します。中央の水位をテストします。通り抜けられた場合、答えはmid以下なので、hi = midに設定します。そうでなければ、答えはmidより大きいので、lo = mid + 1に設定します。両者が一致したとき、その水位が答えです。
5 × 5の例では、lo = 6、hi = 24です。水位15では、上部の領域が閉じているため失敗し、lo = 16になります。水位20、18、17、16ではすべて成功し、hiは16まで下がります。探索は5回の領域塗りつぶしの後、16で終了します。
100 × 100のグリッドには10^4個の水位があるため、判定に必要なテストは約14回で、それぞれO(n²)です。つまり、1.4 × 10^5回ほどのマスの訪問で済み、10^8回の代わりになります。領域塗りつぶしは反復処理にしてください。大きなテストケースの1つは、約5,000マスの長さがある曲がりくねった通路で、Pythonのネストした呼び出しの上限である1,000回をはるかに超える深さになります。
アルゴリズム
loを高い方の隅の高さに、hiをn²-1に設定します。lo < hiの間、mid = (lo + hi) / 2を計算し、小数点以下を切り捨てます。- レベル
midで塗りつぶし探索を行います。右下に到達した場合はhi = midに設定し、そうでなければlo = mid + 1に設定します。 loを返します。
def canReach(grid, t):
# True when you can swim from the top left to the bottom right with the water at height t.
n = len(grid)
seen = [[False] * n for _ in range(n)]
seen[0][0] = True
stack = [(0, 0)]
while stack:
r, c = stack.pop()
if r == n - 1 and c == n - 1:
return True
for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
if 0 <= nr < n and 0 <= nc < n and not seen[nr][nc] and grid[nr][nc] <= t:
seen[nr][nc] = True
stack.append((nr, nc))
return False
def swimInWater(grid):
n = len(grid)
# The answer lies between the higher corner and the highest cell.
lo = max(grid[0][0], grid[n - 1][n - 1])
hi = n * n - 1
# canReach is false below the answer and true from it on: find the first true.
while lo < hi:
mid = (lo + hi) // 2
if canReach(grid, mid):
hi = mid
else:
lo = mid + 1
return lo経路上で最も高いセルにおける Dijkstra
考え方
グリッドをグラフとして扱い、各経路にコストを割り当てます。コストは各ステップの合計ではなく、その経路上で最も高いセルの高さです。このコストでもダイクストラ法は機能します。経路を延長しても、コストが小さくなることはないからです。長い経路のコストは max(old cost, new height) であり、古いコストより小さくなることはありません。これがダイクストラ法に必要な唯一の性質です。
各セルに、そのセルへ至る最良の経路上で最も高いセルの高さを時間として割り当て、最小ヒープに格納します。左上のセルの時間 grid[0][0] から始めます。最小の時間 t を持つセルを取り出し、まだ訪れていない各隣接セルの時間を max(t, its height) とします。右下のセルがヒープから取り出されたとき、その時間が答えです。
セルは、初めてヒープに追加するときに訪問済みとしてマークできます。セルは時間の順にヒープから取り出されるため、ある隣接セルに到達するセルのうち最初のものは、そこに到達しうるすべてのセルの中で最も時間が小さく、そのセルから計算した隣接セルの時間が最小になります。後から到着する経路の時間は、それ以上です。そのため、各セルは最終的な時間で一度だけヒープに追加されます。
これは水位が上がっていく様子を、順を追って示したものです。ヒープには到達可能な領域の境界が保持され、最も低いセルを取り出す操作は、そこへ進める高さまで水位を上げることに相当します。5 × 5 の例では、取り出される順は 0、1、2、3、4、5、そして門のセルである 16 です。その後、迂回路上のすべてのセルの時間が 16 になり、右下のセルは、それより高いセルが取り出される前に、時間 16 でヒープから取り出されます。
n² 個の各セルは最大1回ずつ追加・取り出しされ、それぞれに O(log n) かかるため、時間計算量は O(n² log n) です。また、探索は対象セルが取り出されるとすぐに終了します。
アルゴリズム
- 左上のマスを訪問済みにし、時刻
grid[0][0]でキューに追加します。 - 時刻
tが最小のマスを取り出します。それが右下のマスなら、tを返します。 - まだ訪問していない各隣接マスを訪問済みにし、時刻
max(t, its height)でキューに追加します。 - 手順 2 から繰り返します。
import heapq
def swimInWater(grid):
n = len(grid)
seen = [[False] * n for _ in range(n)]
seen[0][0] = True
# (time, row, col): the time is the highest cell on the best path found to that cell.
heap = [(grid[0][0], 0, 0)]
while True:
t, r, c = heapq.heappop(heap)
# Cells leave the heap in order of time, so this is the earliest you can be here.
if r == n - 1 and c == n - 1:
return t
for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
if 0 <= nr < n and 0 <= nc < n and not seen[nr][nc]:
# Reached for the first time from the cell with the smallest time:
# no later route can arrive earlier, so mark it now.
seen[nr][nc] = True
heapq.heappush(heap, (max(t, grid[nr][nc]), nr, nc))
落とし穴と境界ケース
間違った答えの原因の多くは、見落とした隅のマス、最大値を取るべきところで足し算をしてしまうこと、または探索を早く打ち切りすぎることです。
- スタート地点のマス自体の高さを無視すること。左上のマスは水没する前には通れないため、答えは少なくとも
grid[0][0]です。[[3, 0], [1, 2]]の場合、答えは3です。 - ゴール地点の高さを無視すること。右下のマスも水没している必要があるため、答えは少なくとも
grid[n-1][n-1]です。 - 現在のマスから最も低い隣のマスへ貪欲に進むこと。5 × 5 の例のように、最適な経路ではゲートまで登ってから遠回りする場合があります。到達した領域の境界全体を探索して初めて見つけられます。
- 通常の最短経路のように、経路上の高さを足し合わせること。新しい時刻は
max(t, height)であり、t + heightではありません。 - 領域の塗りつぶしに再帰を使うこと。曲がりくねった経路は数千マスにも及ぶことがあり、Python の再帰呼び出し上限である1,000を超えてしまいます。
- 斜めに移動すること。移動できるのは、現在のマスと辺を共有するマスだけです。
よくある質問4
Swim in Rising Water の時間計算量はどれくらいですか？
ダイクストラ法では O(n² log n)：n² 個の各セルは、最大 n² 個の要素を持つヒープに、それぞれ高々 1 回追加され、取り出されます。水位に対する二分探索も同じ計算量で、O(n²) の塗りつぶしを約 log2(n²) 回行います。どちらも、訪問済みマークとヒープまたはスタックに O(n²) のメモリを使用します。
コストが最も高いセルの場合、ダイクストラ法はなぜ機能するのでしょうか？
Dijkstra 法に必要なのは、経路を延長してもコストが下がらないという性質です。ここで新しいコストは max(t, height) であり、t を下回ることはないため、この性質は成り立ちます。そのため、セルが初めてヒープから取り出された時点で、その時刻は確定しており、目的地に到達したら終了できます。
Rising Water in Swimは二分探索で解けますか？
はい。レベル t で渡れるかどうかは、答えより低いすべてのレベルで偽、答え以上では真です。テストとして塗りつぶしを使い、t を二分探索すると、約 log2(n²) 回のテストで答えが見つかります。100 × 100 のグリッドなら14回です。
Union-Findで「水位の上昇に伴う水泳」を解けるでしょうか？
はい。高さの順にセルを開き、新しく開いたセルを隣接する開いたセルと結合して、左上と右下が同じ集合になった時点で停止します。最後に開いたセルの高さが答えです。グリッドには 0 から n²-1 までの各値が一度ずつ含まれるため、高さからセルへのテーブルを使えば、ソートせずに開く順序を得られます。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
Python
def swimInWater(grid):
# ここにコードを書いてくださいケース1
ケース2
ケース3
入力
grid = [[0, 2], [3, 1]]
期待値
2