脱出BOJ 3055

https://www.acmicpc.net/problem/3055
時間1秒、メモリ128 MB
input :

R C (1 <= R, C <= 50)

R行に地図があります.

「D」と「S」がそれぞれ1つずつあります.

output :

出力ハリネズミがタヌキの巣に移動する最速時間.タヌキ洞まで安全に移動できない場合は「KAKTUS」

条件:
|뉭뉭の森の地図はR行C列からなる.「空いているところは」.水が満ちる地域は「*」、石は「X」と表示されます.ビーバーの穴は「D」、ハリネズミの位置は「S」です.

水も毎分空白の格子に広がります.水のある格子に隣接する空白の格子(少なくとも1つの辺を共有する)は水になります.

ハリネズミは、現在のセルに隣接する4つのセルの1つ

に毎分移動します.

水とハリネズミは石を通ることができません.

ハリネズミは水がいっぱいの地域に移動できず、水もビーバーの巣に移動できない.

まず、水は毎分空の格子に拡張されるので、タヌキが移動する前に、水は先に拡張しなければなりません.
タヌキが動いている場合は、空き地か到着点かを確認しなければなりません.
このようにwhile門を通ってお湯を広げ、タヌキを動かします.実行を続行します.
この場合、ビーバーが移動中にゴールに達したかどうかを決定する変数を設定する必要があります.
拡張水の場合は,これまで存在していた水をキューに保存し,BFSをこの長さで実行させる.もっと多いのは時間が過ぎたからです.
ハリネズミの移動方法も上と同じです.
ハリネズミがこれ以上移動するスペースがなければ、ホワイトゲートを出て「KAKTUS」を出力させる.タヌキの穴に入ったら、whileゲートを回っている間にifゲートでexit(0)に遭遇して逃げてしまいました.

import sys
from collections import deque

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

def water():
    times = len(obstacle)
    for i in range(times):
        x, y = obstacle.popleft()

        for j in range(4):
            next_x = x + dx[j]
            next_y = y + dy[j]

            if next_x < 0 or next_x >= r or next_y < 0 or next_y  >= c:
                continue

            if data[next_x][next_y] == ".":
                data[next_x][next_y] = "*"
                obstacle.append((next_x, next_y))

def bfs():
    times = len(q)

    for i in range(times):
        now_x, now_y = q.popleft()

        for j in range(4):
            next_x = now_x + dx[j]
            next_y = now_y + dy[j]

            if next_x < 0 or next_x >= r or next_y < 0 or next_y >= c:
                continue

            if data[next_x][next_y] == ".":
                data[next_x][next_y] = "S"
                q.append((next_x, next_y))

            if data[next_x][next_y] == "D":
                return 1;
    return 0;

r, c = map(int, sys.stdin.readline().split())
data = []

obstacle = deque()
q = deque()
for i in range(r):
    temp = list(sys.stdin.readline().strip())

    for idx, item in enumerate(temp):
        if item == "S":
            q.append((i, idx))
        elif item == "*":
            obstacle.append((i, idx))

    data.append(temp)

cnt = 0
while q:
    cnt += 1
    water()
    ret = bfs()

    if ret == 1:
        print(cnt)
        exit(0)

print("KAKTUS")