ABC007 C - 幅優先探索 - ペンギンかっこいい

備忘録

問題

回答

import sys

sys.setrecursionlimit(10000000)
import os
import math
import bisect
import collections
import itertools
import heapq
import re
import queue

# import fractions

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)
# lcm = lambda x, y: (x * y) // fractions.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    H, W = il()
    sy, sx = il()
    gy, gx = il()
    C = [iss() for _ in range(H)]
    visit = [[0] * W for _ in range(H)]
    fifoqu = queue.Queue()
    fifoqu.put([sy-1,sx-1])

    MOVE = [[1, 0], [0, 1], [-1, 0], [0, -1]]
    while not fifoqu.empty():
        h, w = fifoqu.get()

        for m in MOVE:
            nexth, nextw = h + m[0], w + m[1]
            if 0 > nexth or nexth >= len(C) or 0 > nextw or nextw >= len(C[0]):
                continue

            if C[nexth][nextw] == '#':
                continue

            if visit[nexth][nextw] != 0:
                continue

            visit[nexth][nextw] = visit[h][w] + 1
            fifoqu.put([nexth, nextw])

    print(visit[gy - 1][gx - 1])


if __name__ == '__main__':
    main()

考え方

与えられる二次元盤面と同等の配列(vjsit)を用意し、
スタート地点から深さ優先探索を行う。
スタート地点を0として、左右上下に移動し、

移動範囲内であること（0 <= h < H, 0 <= w < W)
訪問済みではないこと
壁(#)ではないこと

3点を満たしていた場合には移動を行い、
現在のマスの値から+1した値を用意しておいた配列に入力する。
あとは移動可能な全てのマスを移動するまで処理を行う。

実装は先入れ先出しキュー(fifoqu = queue.Queue())を使用した。
スタート地点をキューに入れ、上下左右移動できる場合には、
移動できる先のマスをキューに入れる。
同じ処理をキューが無くなるまで行うことで、全ての移動可能なマスの探索を行うことができる。