AtCoder-ABC213 E - Stronger Takahashi【Python解答例】 - ebisukeプログラミング初心者脱出黙示録

f:id:ebisuke33:20210810213357p:plain

AtCoder Beginner Contest213のE問題についてPythonの解答例を記事にしていきます。
AtCoder Beginner Contest 213 - AtCoder

AtCoder Beginner Contest213 E - Stronger Takahashi

問題文

H 行 W 列の格子状の区画に区切られた街があります。上から i 行目、左から j 列目の区画は、Si,j が . のとき道、# のとき塀です。

高橋君は自分の家から魚屋に買い物に行くことにしました。高橋君の家は街の左上隅の区画にあり、魚屋は街の右下隅の区画にあります。

高橋君は、自分がいる区画から上下左右に隣接する道の区画に移動することができます。街の外に出ることはできません。
塀の区画に移動することはできませんが、高橋君は非常に腕力が強いため、パンチを 1 回繰り出すことで任意の 2×2 の区画内の塀を壊して道にすることができます。

高橋君が魚屋にたどり着くためには、最低何回パンチを繰り出せばよいか求めてください。

制約

・2 ≤ H,W ≤ 500
・H,W は整数
・Si,j は . または #
・S1,1 と SH,W は .

解答例

from collections import deque

# 入力
h, w = map(int,input().split())
maze = []   # 迷路の文字配列
for _ in range(h):
    maze.append(input())

# スタート、ゴール地点
sx = 0
sy = 0
gx = w-1
gy = h-1

# 各座標へ到達するまでに必要なパンチの数（INFで初期化）
INF = int(1e9)
score = [[INF] * w for _ in range(h)]

# 4方向の移動ベクトル
dx = [1,0,-1,0]
dy = [0,1,0,-1]


# スタートからゴールへのscoreを求めるbfs
def bfs():
    que = deque()
    que.append([sy,sx]) # スタート地点をキューに入れる
    score[sy][sx] = 0 # スタート地点のscoreを0とする

    # キューが空になるまで探索
    while len(que) != 0:
        y, x = que.popleft() # キューの先頭から取り出す
        if y == gy and x == gx: # ゴールなら探索終了
            break
        tmp = score[y][x]
        # (x,y)から4方向に移動 移動後の点は(nx,ny)
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            # 移動先が迷路外ならスキップ
            if nx < 0 or nx >= w or ny < 0 or ny >= h:
                continue
            # 移動先が壁でないならqueの先頭にpush
            if maze[ny][nx] != "#" and score[ny][nx] > tmp:
                score[ny][nx] = tmp
                que.appendleft([ny,nx])
        # パンチをうって移動できる位置に移動 移動後の点は(nx,ny)
        for i in range(-2,3):
            for j in range(-2,3):
                ny = y + i
                nx = x + j
                # 移動先が迷路外やパンチ範囲外の距離ならスキップ
                if nx < 0 or nx >= w or ny < 0 or ny >= h or abs(i)+abs(j)>3:
                    continue
                # パンチ移動後のスコアが低ければ更新しqueの後ろに格納
                if score[ny][nx] > tmp + 1:
                    score[ny][nx] = tmp + 1   # scoreは+1
                    que.append([ny,nx])

    return score[gy][gx]

ans = bfs()
print(ans)