SLIKAR

문제

사악한 암흑의 군주 임정택은 드디어 원하던 마법 구슬을 손에 넣었고, 알랩숲에 홍수를 일으켰다! 이 숲에 살고 있는 고슴도치는 지금 당장 비버의 굴로 가능한 빨리 돌아가 홍수를 피하려고 한다.

알랩숲의 지도는 R행 C열로 구성되어 있다. 비어있는 곳은 '.'로 나타나 있고, 물이 차있는 지역은 '*', 돌은 'X'로 표현되어 있다. 추가적으로, 비버의 굴은 'D'로, 고슴도치의 위치는 'S'로 표시되어 있다.

매 분마다 고슴도치는 현재 있는 칸과 인접한 네 칸 중 하나로 이동할 수 있다. (위, 아래, 오른쪽, 왼쪽) 물은 매 분마다 물이 있는 칸과 적어도 한 변을 공유하는 비어있는 모든 칸에 물이 차게 된다. 물과 고슴도치는 돌을 통과할 수 없다. 또, 고슴도치는 물로 차있는 구역으로 이동할 수 없고, 물은 비버의 소굴로 이동할 수 없다.

알랩숲의 지도가 주어졌을 때, 고슴도치가 안전하게 비버의 굴로 도달하기 위해 필요한 최소 시간을 구하는 프로그램을 작성하시오.

고슴도치는 물이 찰 예정인 칸으로 이동할 수 없음에 주의한다.

 

입력

첫째 줄에 50보다 작거나 같은 자연수 R과 C가 주어진다.

다음 R개 줄에 걸쳐 C개의 문자가 주어진다.('.', '*', 'X', 'D' or 'S') 'D'와 'S'는 하나씩만 주어진다.

 

출력

첫째 줄에 고슴도치가 비버의 굴로 도달할 수 있는 가장 빠른 시간을 출력한다. 만약, 안전하게 비버의 굴로 이동할 수 없을 경우, "KAKTUS"를 출력한다.

 

예제 입력 1

3 3

D.*

...

.S.

예제 출력 1

3

예제 입력 2

3 3

D.*

...

..S

예제 출력 2

KAKTUS

예제 입력 3

3 6

D...*.

.X.X..

....S.

예제 출력 3

6

예제 입력 4

5 4

.D.*

....

..X.

S.*.

....

예제 출력 4

4

 

#코드

import sys
from collections import deque
 
# 알랩숲의 지도는 R행 C열로 구성되어 있다.
# 비어있는 곳은 '.'로 나타나 있고, 물이 차있는 지역은 '*', 돌은 'X'로 표현되어 있다. 
# 비버의 굴은 'D'로, 고슴도치의 위치는 'S'로 표시되어 있다.
# 매 분마다 고슴도치는 현재 있는 칸과 인접한 네 칸 중 하나로 이동할 수 있다. (위, 아래, 오른쪽, 왼쪽) 
# 물은 매 분마다 물이 있는 칸과 적어도 한 변을 공유하는 비어있는 모든 칸에 물이 차게 된다.
# 물과 고슴도치는 돌을 통과할 수 없다
# 고슴도치는 물로 차있는 구역으로 이동할 수 없고, 물은 비버의 소굴로 이동할 수 없다.
# 알랩숲의 지도가 주어졌을 때, 고슴도치가 안전하게 비버의 굴로 도달하기 위해 필요한 최소 시간을 구하는 프로그램을 작성하시오.
# 고슴도치는 물이 찰 예정인 칸으로 이동할 수 없음에 주의한다.
 
# '.' :  0
# 'x' : -1
# '*' :  -2
 
def bfs():
  
  global getArr, visited, start, end, water 
  
  dy = [-1, 1, 0, 0]
  dx = [0, 0, -1, 1]
  
  endY, endX = end.popleft() 
  
  wsize = 0
  ssize = 0
  cnt   = 0
  while True:
    if cnt == 0:
      row, col = start.popleft()
      visited[row][col] = True
      start.append((row, col))
      cnt += 1
    # 1. 물이 먼저 퍼진다. (물은 비버의 소굴로 이동할 수 없다.)
    wsize = len(water)
    for _ in range(wsize):  
    #if len(water) > 0:
      wRow, wCol = water.popleft()
      visited[wRow][wCol] = True
      for i in range(4):
        ny = dy[i] + wRow
        nx = dx[i] + wCol 
        if 0<=ny<n and 0<=nx<m and visited[ny][nx] == False and getArr[ny][nx] == 0 : 
          if ny == endY and nx == endX: continue
          getArr[ny][nx] = -2
          water.append((ny,nx))
          visited[ny][nx] = True
    # 2. 고슴도치가 이동한다. (고슴도치는 물로 차있는 구역으로 이동할 수 없다.)  
    ssize = len(start) 
    for _ in range(ssize):
    #if len(start) > 0:
      row, col = start.popleft()
      visited[row][col] = True
      for i in range(4):
        ny = dy[i] + row
        nx = dx[i] + col 
        if 0<=ny<n and 0<=nx<m and visited[ny][nx] == False and getArr[ny][nx] == 0:
          if getArr[ny][nx] == -2: continue
          
          getArr[ny][nx] = getArr[row][col] + 1
          start.append((ny,nx))
          visited[ny][nx] = True
          
    if not start and not water: return getArr[endY][endX]    
  
 
if __name__ == "__main__":
  input = sys.stdin.readline
  
  n, m       = map(int, input().split())
  getArr     = [[0]*m for _ in range(n)]
  visited    = [[False]*m for _ in range(n)]
  start, end = deque(), deque()
  water      = deque()
  for i in range(n):
    row = input().strip()
    for j in range(m):
      if row[j] == '*':
        getArr[i][j] = -2
        water.append((i, j))
      elif row[j] == 'X':
        getArr[i][j] = -1
      elif row[j] == 'D':
        end.append((i, j))
      elif row[j] == 'S':
        start.append((i, j))
        
  
        
  result = bfs() 
  if result == 0:
    print('KAKTUS')
  else:
    print(result)
  ''' 
  for i in getArr:
    for j in i:
      print(j, end=' ')
    print()
 '''