Pythonで解くAtCoder(ABC176:D)
こんにちは、クルトンです！
この記事では
AtCoderの「AtCoder Beginner Contest 176」のD問題をPythonを使って解説します。
問題のリンクを載せておきます。
サンプルコードの解説
上記のサンプルコードの内容を解説します。
from collections import deque
01-BFSを使って解いているので両端キューをインポートしています。
また、この問題は先頭と末尾の両方から要素を追加するので両端キューでしか解けませんが、普通のBFSはキューを使って解きます。
しかし、実行速度を比較するとQueueを使うよりもdequeをキューとして使った方が速いので、結局BFSではdequeを使うことになります。
BFSの中には、dequeでは間に合ってもQueueを使うと間に合わないものもあるのでしっかりと覚えておきましょう。
H, W = map(int,input().split()) CH, CW = map(int,input().split()) DH, DW = map(int,input().split()) S = [] for _ in range(H): S.append(list(input()))
入力を受け取っています。
d = [[-1 for i in range(W)] for j in range(H)]
ワープ魔法を使う回数を記録する2次元リストです。
最終的な答えとなります。
Q = deque([[CH - 1, CW - 1, 0]])
dequeを作ります。
スタート地点の座標とワープ魔法を使う回数を入力しておきます。
スタート地点ではワープ魔法を使わないので回数は0になります。
while len(Q) != 0: x, y, cnt = Q.popleft() if d[x][y] != -1: continue d[x][y] = cnt for tx in range(-2, 3): for ty in range(-2, 3): nx = x + tx ny = y + ty if 0 <= nx < H and 0 <= ny < W and S[nx][ny] == ".": if abs(tx) + abs(ty) == 1: Q.appendleft([nx, ny, cnt]) elif abs(tx) + abs(ty) >= 2: Q.append([nx, ny, cnt + 1])
少し長いですが、01-BFSのところをまとめて説明します。
while len(Q) != 0:
Qの要素が0になるまでループを繰り返します。
x, y, cnt = Q.popleft()
if d[x][y] != -1:
continue
d[x][y] = cnt
この部分では、まず座標とワープ魔法の回数を受け取ります。
そして、その座標を既に訪れたことがあればcontinueで処理をスキップします。
また、その座標をまだ訪れていなかった場合には、d[x][y]にワープ魔法の回数を代入します。
for tx in range(-2, 3): for ty in range(-2, 3): nx = x + tx ny = y + ty if 0 <= nx < H and 0 <= ny < W and S[nx][ny] == ".": if abs(tx) + abs(ty) == 1: Q.appendleft([nx, ny, cnt]) elif abs(tx) + abs(ty) >= 2: Q.append([nx, ny, cnt + 1])
この部分ではQに要素を追加しています。
txは縦方向の、tyは横方向の移動距離を表しています。
このとき、魔法を使わずに移動できる距離が
(tx, ty) = (1, 0), (0, 1), (-1, 0), (0, -1)
であることから、絶対値の和が1であれば魔法を使わずに移動できることが分かります。
上のコードではこのことを使って場合分けを行っています。
このとき、解説に載っているように、魔法を使わずに移動できる座標を先頭に、魔法を使ってしか移動できない座標を末端に追加しています。
また当然ですが、魔法を使って移動した座標におけるcnt（ワープ魔法を使った回数）は1増やしています。
以上が0-1BFSのコードになります。
print(d[DH - 1][DW - 1])
最後に答えを出力して終了です。
まとめ
今回は
- 0-1BFSで解く
という問題でした。
ではまたお会いしましょう！さようなら～
