Swim in Rising Water
0 から n²-1 までのすべての数がちょうど1回ずつ含まれる、高さを表す n × n のグリッドが与えられます。時刻 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では、最初の経路は水没しています。
- 入力
- 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から15、14、13、12、11、そして最下段を回っても、16を超えることはありません。
- 入力
- grid = [[3, 0], [1, 2]]
- 出力
- 3
- 説明
- 開始セルの高さは3なので、時刻3になる前はそのセルにいることも、そこから出ることもできません。その時点までに、グリッド全体が水没しています。
発展問題
高さが重複し、10^9に達する可能性がある場合、どの方法なら変更せずにそのまま使えますか。また、何を対象に二分探索しますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
水位
tがわかっているとします。通り抜けられる道があるかどうか、わかりますか？tが大きくなるにつれて、その答えはどのように変わりますか？経路上のすべてのセルが水で覆われる必要があるため、経路に必要な時間は、その経路上で最も高いセルによって決まります。両端の角を結ぶ経路のうち、最も高いセルができるだけ低い経路を見つけましょう。
テストとして塗りつぶし探索を行いながら
tについて二分探索するか、セルの時刻を到達時刻とセル自体の高さの大きい方として、最小ヒープを使ってダイクストラ法を実行します。右下のセルがヒープから取り出されたら終了します。
解説
通過するすべてのセルを水が覆う必要があるため、経路にかかる時間は、その経路上で最も標高の高いセルにかかる時間と同じです。そこで、両端の角の間で、経路上の最高セルが最も低くなる経路を見つけます。つまり、コストが合計ではなく最大値となる最短経路です。水位を少しずつ上げるか、水位を二分探索するか、そのコストに対してダイクストラ法を実行します。
水位を一段ずつ上げる
正しいが、最大のテストでは終わらない
考え方
水位 t を固定します。左上から、高さが t 以下のマスを通って塗りつぶし探索を1回行えば、右下に到達できるかどうかがわかります。両方の角が水面下にある必要があるため、max(grid[0][0], grid[n-1][n-1]) のように、高いほうの角の高さを t の初期値とし、探索が右下まで到達するまで1ずつ増やします。水位が上がると通れるマスが増えるだけなので、最初に到達できた水位が答えです。
探索1回の計算量は O(n²) で、水位はほぼ n² 回上昇する可能性があります。100 × 100 のグリッドでは、水位が最大 10^4 段階 × 10^4 マスとなり、訪問するマスは約 10^8 個です。
アルゴリズム
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水位に対する二分探索
考え方
洪水填充测试在答案以下的每个水位都会失败，从答案开始的每个水位都会成功。二分查找会找到这个转折点，它位于较高的角落和 n²-1 之间，此时整个网格都被水淹没。
在 5 × 5 的示例中，lo = 6 且 hi = 24。水位 15 时测试失败，因此 lo = 16。水位 20、18、17 和 16 时测试都成功，经过五次填充后，搜索在 16 结束。
100 × 100 的网格有 10^4 个水位，因此大约 14 次填充就能确定答案：约 1.4 × 10^5 次单元格访问，而不是 10^8 次。
アルゴリズム
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ルート上で最も高いセルにおけるダイクストラ法
考え方
各ルートに、そのルート上で最も高いマスの高さをコストとして割り当てます。ある高さ h のマスへルートを延ばすコストは max(old cost, h) であり、以前のコストより小さくなることはないため、ダイクストラ法は引き続き使えます。その時刻をキーとするセルの最小ヒープを用意し、左上のセルを grid[0][0] として開始します。右下のセルがヒープから取り出されたとき、その時刻が答えです。
セルは最初に追加した時点で訪問済みとしてマークできます。セルは時刻順にヒープから取り出されるため、隣接するセルに最初に到達したセルが、そのセルに到達しうる最小の時刻を与え、各セルはヒープに一度だけ追加されます。
ヒープには到達可能な領域の境界が保持され、取り出すたびに、そこへ進むのにちょうど十分な高さまで水位が上がります。5 × 5 の例では、取り出される時刻は 0、1、2、3、4、5 と続き、その後、16 にある門を通り、右下のセルが時刻 16 で取り出されます。
アルゴリズム
- 左上のマスを訪問済みとしてマークし、時刻
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]とgrid[n-1][n-1]の高さ以上です。[[3, 0], [1, 2]]の場合、答えは3です。 - 最も低い隣接マスへ貪欲に進む。5 × 5の例のように、最適な経路ではゲートまで登ってから遠回りする場合があります。
- 通常の最短経路のように、経路上の高さを足し合わせる。新しい所要時間は
max(t, height)であり、t + heightではありません。 - 塗りつぶし処理に再帰を使う。曲がりくねった経路は何千マスもの長さになることがあり、Pythonのネストした呼び出しの上限である1,000回を超えてしまいます。
よくある質問3
Rising Water における Swim の時間計算量はどれくらいですか？
Dijkstra のアルゴリズムでは O(n² log n)：n² 個のセルは、それぞれヒープに高々 1 回追加され、取り出されます。水位に対する二分探索も同じ計算量で、O(n²) の塗りつぶし処理を約 log2(n²) 回行います。どちらも O(n²) のメモリを使用します。
Rising Water の中で泳ぐ問題は二分探索で解けるでしょうか？
はい。レベル t で渡れるかどうかは、答えのところで一度だけ、false から true に切り替わります。判定に塗りつぶし探索を使って t を二分探索すると、塗りつぶし探索はおよそ log2(n²) 回必要で、100 × 100 のグリッドなら 14 回です。
Union-Findで「水位の上昇に伴う水泳」の問題を解けますか？
はい。高さの順にセルを開き、新しく開いた各セルを隣接する開いたセルと結合し、2つの角が同じ集合に属した時点で停止します。最後に開いたセルの高さが答えです。0からn²-1までの各値は1回ずつ現れるため、高さからセルへの対応表を使えば、ソートせずに順序がわかります。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def swimInWater(grid):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
grid = [[0, 2], [3, 1]]
期待される出力
2