SamCoding Round 11 (Div. 1) C - Ice Maze
- サイト
- SamCoding
- コンテスト
- SamCoding Round 11 (Div. 1)
- 問題
- C - Ice Maze(常設版)
の氷の盤面で、S から出発して穴 E に到達するまでの最小の滑走回数を求める問題です()。# は岩、それ以外のマスは氷です。
回の滑走では上下左右のいずれかに進み、次のマスが岩または盤面の外になるまで止まれません。ただし、途中で E を通過したらその場で穴に落ち、到達したものとします。到達できない場合は を出力します。
位置と進行方向を状態にする
Section titled “位置と進行方向を状態にする”滑走を始めるたびに止まる位置まで走査すると、同じ通路を何度も調べてしまいます。そこで、滑走を マスずつの移動に分け、位置に加えて進行方向も状態に持たせます。
dp[k][i][j] を、「マス に方向 に滑っている状態で到達するまでの最小の滑走回数」とします。遷移は次の 種類です。
- 進行方向の隣のマスに進める場合は、そのマスへ同じ方向で移動する。滑走中なので追加コストは 。
- 進行方向が岩または盤面の外で塞がれている場合は、その場で次の滑走の方向を選ぶ。新しい滑走を始めるので追加コストは 。
進める間は方向を変える遷移を作らないことで、途中で止まれないという条件を表せます。塞がれた方向を選ぶ遷移もコードには含まれますが、移動せずに回数が増えるだけなので、最小値を改善することはありません。
0-1 BFS で最小回数を求める
Section titled “0-1 BFS で最小回数を求める”辺のコストが または なので、0-1 BFS を使います。コスト の遷移で更新した状態は deque の先頭へ、コスト の遷移で更新した状態は末尾へ追加します。
最初の滑走の方向は自由に選べるので、S の 方向の状態をすべて距離 で初期化します。
答えは、E にある 方向の状態の距離の最小値です。滑走中の各マスを状態にしているので、停止位置になるかどうかによらず、E を通過した時点の回数を求められます。コードでは E から先にも探索を続けますが、そこから先のコストも非負なので、E に初めて到達するまでの最小値は変わりません。
状態数は で、各状態からの遷移は高々 本です。よって、計算量・空間計算量ともに です。
Python
from itertools import productfrom collections import deque
N, M = map(int, input().split())G = [input() for i in range(N)]INF = 10**10dp = [[[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] = 1while 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 = INFfor 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)