문제
사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제일 친한 친구인 비버의 굴로 가능한 빨리 도망가 홍수를 피하려고 한다.
티떱숲의 지도는 R행 C열로 이루어져 있다. 비어있는 곳은 '.'로 표시되어 있고, 물이 차있는 지역은 '*', 돌은 'X'로 표시되어 있다. 비버의 굴은 'D'로, 고슴도치의 위치는 'S'로 나타내어져 있다.
매 분마다 고슴도치는 현재 있는 칸과 인접한 네 칸 중 하나로 이동할 수 있다. (위, 아래, 오른쪽, 왼쪽) 물도 매 분마다 비어있는 칸으로 확장한다. 물이 있는 칸과 인접해있는 비어있는 칸(적어도 한 변을 공유)은 물이 차게 된다. 물과 고슴도치는 돌을 통과할 수 없다. 또, 고슴도치는 물로 차있는 구역으로 이동할 수 없고, 물도 비버의 소굴로 이동할 수 없다.
티떱숲의 지도가 주어졌을 때, 고슴도치가 안전하게 비버의 굴로 이동하기 위해 필요한 최소 시간을 구하는 프로그램을 작성하시오.
고슴도치는 물이 찰 예정인 칸으로 이동할 수 없다. 즉, 다음 시간에 물이 찰 예정인 칸으로 고슴도치는 이동할 수 없다. 이동할 수 있으면 고슴도치가 물에 빠지기 때문이다.
# 3055
import sys
input = lambda: sys.stdin.readline().strip()
from collections import deque
r, c = map(int, input().split())
arr = [list(map(str, input())) for _ in range(r)]
dx, dy = [-1, 0, 1, 0], [0, 1, 0, -1]
check = set(["*", "X"])
amur_x, amur_y = 0, 0
end_x, end_y = 0, 0
start_water = []
for x in range(r):
for y in range(c):
if arr[x][y] == ".":
arr[x][y] = -1
elif arr[x][y] == "*":
start_water.append((x, y))
elif arr[x][y] == "D":
end_x, end_y = x, y
arr[x][y] = -1
elif arr[x][y] == "S":
amur_x, amur_y = x, y
arr[x][y] = 0
def bfs(start_water, amur_x, amur_y):
global r, c, arr, dx, dy, check, end_x, end_y
queue = deque()
queue.append((amur_x, amur_y))
for x, y in start_water:
queue.append((x, y))
while queue:
x, y = queue.popleft()
for i in range(4):
nx, ny = x + dx[i], y + dy[i]
if nx < 0 or ny < 0 or nx >= r or ny >= c:
continue
if arr[nx][ny] in check:
continue
if arr[x][y] == "*":
if (nx, ny) != (end_x, end_y):
arr[nx][ny] = "*"
queue.append((nx, ny))
else:
if arr[nx][ny] == -1 or arr[x][y] + 1 < arr[nx][ny]:
arr[nx][ny] = arr[x][y] + 1
queue.append((nx, ny))
bfs(start_water, amur_x, amur_y)
if arr[end_x][end_y] > 0:
print(arr[end_x][end_y])
else:
print("KAKTUS")