ebisukeプログラミング初心者脱出黙示録

30歳を過ぎてから始めたプログラミングと競プロの記録。Pythonで取り組んでいます。Arduinoで電子工作も

【AtCoder版!蟻本】ARC 005 C - 器物損壊!高橋君【幅優先探索】

f:id:ebisuke33:20210319000747p:plain
AtCoder版!蟻本幅優先探索で類題としてあげられているAtCoder Regular Contest 005 C - 器物損壊!高橋君をPythonで解いていきます。

C - 器物損壊!高橋君

AtCoder Regular Contest 005 C - 器物損壊!高橋君

問題文

良く見てみるとカードの有効期限が切れていたので、高橋君は諦めて魚屋に直接うなぎを買いに行くことにしました。
 彼の住む街は長方形の形をしており、格子状の区画に区切られています。区画は道または塀のどちらかであり、高橋君は道を東西南北に移動できますが斜めには移動できません。また、塀の区画は通ることができません。高橋君の家から魚屋までの道のりは非常に複雑なため、単純に歩くだけでは辿り着くことは困難です。
 しかし、高橋君は腕力には自信があるので道に上下左右で面している塀を 2 回までなら壊して道にすることができます。

 高橋君が魚屋に辿り着くことができるかどうか答えてください。

入力

・入力は H+1 行ある。
・1 行目は、街の南北の長さとして整数 H(1≦H≦500) と東西の長さとして整数 W(1≦W≦500) が空白で区切られて与えられる。
・2 行目からの H 行には、格子状の街の各区画における状態 c(i,j)(0≦i≦H−1, 0≦j≦W−1) が与えられる。
・i 行目 j 文字目の文字 c(i,j) はそれぞれ s, g, ., # のいずれかで与えられ、座標 (j,i) が下記のような状態であることを表す。
・s : その区画が家であることを表す。
・g : その区画が魚屋であることを表す。
・. : その区画が道であることを表す。
・# : その区画が塀であることを表す。
・高橋君は家・魚屋・道は通ることができるが、塀は通ることができない。
・与えられた街の外を通ることはできない。
・s と g はそれぞれ 1 つずつ与えられる。

解答例

from collections import deque

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

# スタート、ゴールの探索
for y in range(h):
    for x in range(w):
        if maze[y][x] == "s": # スタート座標はsx,sy
            sx = x
            sy = y
        if maze[y][x] == "g": # ゴール座標はgx,gy
            gx = x
            gy = y

# scoreは各座標へ到達するまでに壊す必要のある壁の数(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:
        p = que.popleft() # キューの先頭から取り出す
        if p[0] == gy and p[1] == gx: # ゴールなら探索終了
            break
        for i in range(4): # pから4方向に移動 移動後の点は(nx,ny)
            ny = p[0] + dy[i]
            nx = p[1] + 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] == INF:
                # scoreは+1
                score[ny][nx] = score[p[0]][p[1]] + 1
                que.append([ny,nx])
            # 移動先が壁でなく未到達ならqueの先頭にpush
            if maze[ny][nx] != "#" and score[ny][nx] == INF:
                # scoreはpと同じ
                score[ny][nx] = score[p[0]][p[1]]
                que.appendleft([ny,nx])

    return score[gy][gx]

res = bfs()
if res <= 2:
    print("YES")
else:
    print("NO")

解説

これまでの幅優先探索の問題のようにスタート地点からゴール地点に向かってBFSを行う問題です。
違う点は最短距離を求めるのでなく、壁を2回まで壊してゴールに到着できるかを答える問題です。

今回も迷路と同じ範囲の配列scoreを作成しますが、最短距離でなく壊した壁の数を記録していきます。

bfsではスタート地点をキューに入れて探索を始めます。
探索先が道と壁の場合で、キューの入れ方を変えました。
探索先が道の場合、探索元と同じscoreを記録してキューの先頭に入れます。
壁の場合は、探索元のscoreに+1した数を記録してキューの最後尾に入れました。

キューから先頭からしか取り出さないので、最初は壁を壊さずに行くことができるすべての道に到達するまで探索を続けます。

道の探索が終われば次はscoreが1の壁の探索です。
このとき、また道に出ればscore1として道の探索を行いました。
未探索の壁があればscoreをさらに+1してキューの最後尾に入れます。

このような探索を繰り返していけば、最終的にはゴールまで探索が進み 壊した壁の数がscoreに記録されています。

問題にあわせてscoreが2以下ならYes、それより大きければNoを出力すればOKでした。



AtCoder版!蟻本(初級編)の記事リンクページはこちら
ebisuke33.hatenablog.com