Rotting Oranges
同じ長さの行のリストとして、グリッドが与えられます。各セルは0（空）、1（新鮮なオレンジ）、または2（腐ったオレンジ）です。毎分、腐ったオレンジと上下左右のいずれかで隣接している新鮮なオレンジは、腐ります。新鮮なオレンジがなくなるまでの分数を返してください。ただし、決して腐らない新鮮なオレンジがある場合は-1を返します。最初から新鮮なオレンジがないグリッドの場合、必要な分数は0です。
関数
- gridinteger-2d-array
- グリッド、各行に0、1、2のリスト
- 戻り値integer
- オレンジが新鮮でなくなるまでの分数、またはそのようなことが起こらない場合は -1
制約
1 ≤ grid.length ≤ 1501 ≤ grid[i].length ≤ 150- すべての行の長さは同じです。
- 各
grid[i][j]は0、1、または2です。
例
- 入力
- grid = [[2, 1, 1, 0], [0, 1, 0, 1], [1, 1, 1, 1]]
- 出力
- 6
- 説明
- セルを (行, 列) と表すと、腐ったオレンジは (0,0) にあり、唯一の経路をたどります。1 分後に (0,1)、2 分後に (0,2) と (1,1)、3 分後に (2,1)、4 分後に (2,0) と (2,2)、5 分後に (2,3) に到達します。(1,3) のオレンジは (2,3) にしか接していないため、最後に腐り、6 分後になります。
- 入力
- grid = [[2, 1, 0], [0, 0, 1]]
- 出力
- -1
- 説明
- (1,2) にあるオレンジの上と左には空のセルがあり、下と右ではグリッドが終わっています。腐敗がこのオレンジに到達することはないため、答えは -1 です。
- 入力
- grid = [[0, 2, 0, 2]]
- 出力
- 0
- 説明
- 開始時に新鮮なオレンジはないため、時間が経過する必要はなく、答えは0です。
提出時に隠しテスト+21件
発展問題
腐った隣のオレンジに接したとき、新鮮なオレンジが腐るまでに必要な時間はそれぞれ異なるとします。その場合、完了までの時間をどのように求めますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
腐敗が波のように広がると考えてください。3分目に腐る可能性があるのはどのオレンジでしょうか？2分目に腐ったオレンジの隣にある、新鮮なオレンジだけです。
腐ったオレンジすべてを開始時にキューに入れ、そこから一斉に幅優先探索を行います。キューには常に、腐敗の最前線が保持されます。
キューを1レベルずつ処理します。キューのサイズを読み取り、その数だけセルを取り出し、レベルごとに1分を数えます。新鮮なオレンジの数を最初に数え、腐るたびにその数を減らしていけば、0になった時点ですぐに停止でき、先にキューが空になった場合は -1 を返せます。
解説
腐敗はすべての腐ったオレンジから同時に始まり、1分ごとに1マスずつ広がります。したがって、答えは距離です。最も遠い新鮮なオレンジが、最も近い腐ったオレンジから何歩離れているかを求めます。幅優先探索なら、開始前にすべての腐ったオレンジをキューに入れ、キューを1レベルずつ、つまり1分ごとに処理することで、これを正確に測定できます。
1分ごとにシミュレーションする
正しいが、最大のテストでは終わらない
考え方
ストーリーの指示どおりに処理します。1分ごとにグリッド全体を調べ、腐ったオレンジに接している新鮮なオレンジをすべて列挙します。次に、それらをすべて腐らせ、時計を1進めてから、もう一度調べます。腐らせるオレンジが見つからなくなったら終了します。その時点で新鮮なオレンジがまだグリッドに残っている場合、腐敗がそこまで届くことはありません。-1を返します。
まず列挙し、その後で腐らせます。調べている途中でオレンジを腐らせると、同じ調査中に後から見るセルはそれを腐ったものとして認識し、連鎖して腐ります。そのため、腐敗が1分で複数のセルに広がり、時計の値が実際より小さくなってしまいます。
これは正しい方法ですが、1分ごとに rows × cols 個のセルをすべて調べる必要があり、分数がセル数に近づくこともあります。新鮮なオレンジが1本の曲がりくねった経路を作り、その先頭に腐ったオレンジがある 150 × 150 のグリッドでは、腐敗に11,324分かかります。22,500個のセルを11,324回調べるため、セルのチェック回数は約2.5 × 10^8 回となり、そのほとんどは状態が変化しないセルに対するものです。
アルゴリズム
- minutesを0に設定します。
- グリッドを調べ、腐った隣接マスがある新鮮なオレンジをすべてリストにします。
- リストが空なら停止します。そうでなければ、リストにあるオレンジをすべて腐らせ、minutesに1を加えて、もう一度調べます。
- 新鮮なオレンジが残っていれば-1を返し、そうでなければminutesを返します。
def orangesRotting(grid):
rows, cols = len(grid), len(grid[0])
minutes = 0
while True:
# Find every fresh orange that touches a rotten one right now.
to_rot = []
for r in range(rows):
for c in range(cols):
if grid[r][c] != 1:
continue
for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 2:
to_rot.append((r, c))
break
if not to_rot:
break
# Rot them only after the scan, so the rot moves one step a minute.
for r, c in to_rot:
grid[r][c] = 2
minutes += 1
for row in grid:
if 1 in row:
return -1
return minutesレベルごとのマルチソース BFS
考え方
スキャンでは、処理対象から遠いセルに時間を費やしてしまいます。時刻 t+1 に腐る可能性があるのは、時刻 t に腐ったオレンジの新鮮な隣接オレンジだけです。そこで、腐敗の最前線にあるものだけをキューに入れておきます。
時刻 0 に腐っているオレンジをすべて、まとめてキューに入れて開始します。これがマルチソースの部分です。新鮮なオレンジは、最も近い腐ったオレンジからの距離と同じ時刻に腐ります。すべての始点を登録した幅優先探索では、各セルに最も近い始点から最初に到達します。始点ごとに探索して最小値を求める代わりに、1 回の探索で処理できます。
次に、レベルごとに処理します。各分の開始時点で、キューには直前の分に腐ったオレンジ k 個が入っています。先頭からちょうど k 個を取り出し、それぞれについて新鮮な隣接オレンジを腐らせて、キューの末尾に追加します。k 個すべての処理が終わると 1 分が経過し、キューには次の最前線のオレンジが入っています。最初の例のレベルは {(0,0)}, {(0,1)}, {(0,2), (1,1)}, {(2,1)}, {(2,0), (2,2)}, {(2,3)}, {(1,3)} です。開始から 6 ステップなので、6 分です。
最初に新鮮なオレンジの数を数え、1 個腐るたびにその数を減らします。数が 0 になったらすぐに停止します。そうしないと、最後のレベルで何も腐らないのに 1 分が加算されます。また、残りの数が 0 より大きい状態でキューが空になった場合は -1 を返します。各セルがキューに入るのは最大 1 回で、隣接する 4 セルを確認するため、計算量は O(rows × cols) です。
アルゴリズム
- 腐ったオレンジをすべてキューに入れ、新鮮なオレンジの数を数えます。
- 分数を0に設定します。キューが空でなく、新鮮なオレンジが残っている間、分数に1を加え、キューのサイズ k を記録します。
- 先頭からオレンジを k 個取り出します。グリッド内の隣接する新鮮なオレンジごとに、腐った状態にし、新鮮なオレンジの数を減らして、キューの末尾に追加します。
- ループが終了したら、新鮮なオレンジの数が0なら分数を返し、そうでなければ -1 を返します。
from collections import deque
def orangesRotting(grid):
rows, cols = len(grid), len(grid[0])
queue = deque()
fresh = 0
# Every orange that is rotten at minute 0 starts in the queue.
for r in range(rows):
for c in range(cols):
if grid[r][c] == 2:
queue.append((r, c))
elif grid[r][c] == 1:
fresh += 1
minutes = 0
while queue and fresh > 0:
minutes += 1
# The queue holds exactly the oranges that went rotten last minute.
# Rot their fresh neighbours; those become the next minute's queue.
for _ in range(len(queue)):
r, c = queue.popleft()
for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
grid[nr][nc] = 2
fresh -= 1
queue.append((nr, nc))
return minutes if fresh == 0 else -1
落とし穴と境界ケース
ここでの誤答の多くは1分ずれているか、探索を始める場所を間違えています。
- 最後のレベルにも1分を加えている。キューが空になるまでループを回す場合、最後の処理では何も腐らないのに、さらに1が加算されます。新鮮なオレンジがなくなったらすぐに終了してください。
- 腐ったオレンジを1つずつ起点にして探索している。最初の探索が、到達したオレンジをすべて自分の時計で処理するため、中央で出会うはずの2つの起点があると、時間が長くなりすぎます。
[[2, 1, 1, 1, 1, 1, 1, 2]]にかかる時間は6分ではなく3分です。 - 1分ごとの処理でスキャン中にオレンジを腐らせている。同じスキャンの後の方にあるセルがそれらを腐ったものとして認識し、腐敗が1分で複数のセルに広がってしまいます。
- 腐ったオレンジがないため-1を返している。新鮮なオレンジもなければ、何もする必要はありません。
[[0]]は0を返します。腐らずに残った新鮮なオレンジがある場合に限り、答えは-1になります。 - オレンジをキューに入れるときではなく、キューから取り出すときに腐ったものとしてマークしている。2つの腐ったオレンジに隣接するオレンジはキューに2回入り、新鮮なオレンジの数が0未満になります。
- 深さ優先探索。1つの経路をたどれる限り深く進むため、オレンジに初めて到達した時点では、そのオレンジが何分後に腐るかは分かりません。
よくある質問4
腐ったオレンジの時間計算量はどれくらいですか？
幅優先探索を使うと O(rows × cols) です。最初の走査ではすべてのセルを1回ずつ調べ、各オレンジは最大1回キューに入り、4つの隣接セルを調べます。最悪の場合、つまり腐ったオレンジで埋め尽くされたグリッドでは、キューは O(rows × cols) の領域を使います。
Rotting Orangesでは、なぜDFSではなくBFSを使うのでしょうか？
幅優先探索では、開始地点からの距離順にセルを訪問します。ここでは距離は時間を表します。探索のレベル k は、ちょうど k 分後に腐るオレンジの集合です。深さ優先探索では、最短経路を見つける前に長い迂回路を通ってセルに到達することがあるため、より短い経路を見つけるたびにセルを再訪問する必要があります。
マルチソースBFSとは何ですか？
キュー内の複数のセルを距離 0 として開始する幅優先探索です。1 回の探索で、すべてのセルについて最も近い始点までの距離が求められます。これは、各始点から探索して最小値を取った場合と同じ結果であり、探索 1 回分のコストで済みます。グリッド上で「最も近い X までの距離」を求める問題には、いずれもこの方法を使います。
グリッドを変更せずに「Rotting Oranges」を解けますか？
はい。別途 visited 配列を用意し、グリッドに 2 を書き込む代わりに、それを確認します。その場合、追加で O(rows × cols) のメモリが必要になりますが、キューにもいずれ必要になる可能性があります。グリッドを参照渡しする言語では、グリッドに書き込むと呼び出し元のグリッドも変更されるため、面接官からその点について質問されることがあります。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
Python
def orangesRotting(grid):
# ここにコードを書いてくださいケース1
ケース2
ケース3
入力
grid = [[2, 1, 1, 0], [0, 1, 0, 1], [1, 1, 1, 1]]
期待値
6