コンテンツにスキップ

SamCoding Round 11 (Div. 1) C - Ice Maze

サイト
SamCoding
コンテスト
SamCoding Round 11 (Div. 1)
問題
C - Ice Maze(常設版)

N×MN\times M の氷の盤面で、S から出発して穴 E に到達するまでの最小の滑走回数を求める問題です(N,M≤1000N,M\le 1000)。# は岩、それ以外のマスは氷です。

11 回の滑走では上下左右のいずれかに進み、次のマスが岩または盤面の外になるまで止まれません。ただし、途中で E を通過したらその場で穴に落ち、到達したものとします。到達できない場合は −1-1 を出力します。

滑走を始めるたびに止まる位置まで走査すると、同じ通路を何度も調べてしまいます。そこで、滑走を 11 マスずつの移動に分け、位置に加えて進行方向も状態に持たせます。

dp[k][i][j] を、「マス (i,j)(i,j) に方向 kk に滑っている状態で到達するまでの最小の滑走回数」とします。遷移は次の 22 種類です。

  • 進行方向の隣のマスに進める場合は、そのマスへ同じ方向で移動する。滑走中なので追加コストは 00。
  • 進行方向が岩または盤面の外で塞がれている場合は、その場で次の滑走の方向を選ぶ。新しい滑走を始めるので追加コストは 11。

進める間は方向を変える遷移を作らないことで、途中で止まれないという条件を表せます。塞がれた方向を選ぶ遷移もコードには含まれますが、移動せずに回数が増えるだけなので、最小値を改善することはありません。

辺のコストが 00 または 11 なので、0-1 BFS を使います。コスト 00 の遷移で更新した状態は deque の先頭へ、コスト 11 の遷移で更新した状態は末尾へ追加します。

最初の滑走の方向は自由に選べるので、S の 44 方向の状態をすべて距離 11 で初期化します。

答えは、E にある 44 方向の状態の距離の最小値です。滑走中の各マスを状態にしているので、停止位置になるかどうかによらず、E を通過した時点の回数を求められます。コードでは E から先にも探索を続けますが、そこから先のコストも非負なので、E に初めて到達するまでの最小値は変わりません。

状態数は 4NM4NM で、各状態からの遷移は高々 44 本です。よって、計算量・空間計算量ともに O(NM)O(NM) です。

Python
from itertools import product
from collections import deque
N, M = map(int, input().split())
G = [input() for i in range(N)]
INF = 10**10
dp = [[[INF for j in range(M)] for i in range(N)] for k in range(4)]
q = deque()
for i, j in product(range(N), range(M)):
if G[i][j] != "S":
continue
for k in range(4):
q.append((k, i, j))
dp[k][i][j] = 1
while q:
k, i, j = q.popleft()
di, dj = [(-1, 0), (1, 0), (0, -1), (0, 1)][k]
ni, nj = i + di, j + dj
if ni in range(N) and nj in range(M) and G[ni][nj] != "#":
if dp[k][ni][nj] > dp[k][i][j]:
dp[k][ni][nj] = dp[k][i][j]
q.appendleft((k, ni, nj))
else:
for nk in range(4):
if dp[nk][i][j] > dp[k][i][j] + 1:
dp[nk][i][j] = dp[k][i][j] + 1
q.append((nk, i, j))
ans = INF
for i, j in product(range(N), range(M)):
if G[i][j] != "E":
continue
for k in range(4):
ans = min(ans, dp[k][i][j])
if ans == INF:
print(-1)
else:
print(ans)