#백준_3055 탈출 - Java 자바

# 유형 : 탐색, 시뮬레이션

# 기존의 bfs를 사용하면서 동시에 물이 차오르는 것(물이 다음에 차오를 곳은 못간다) 을 생각해야 하기 때문에 큐를 한개 더 써서 물차오르는 것을 먼저 처리해주고, 그다음 고슴도치가 움직이게 하였다. 

# 간단히 말하면, 물 차오르는 큐를 하나 만들어 고슴도치가 움직이기전에 탐색을 돌려 차오르는 곳을 처리해주고, 그 다음 고슴도치가 움직일수있는 위치들을 반복문을 통해 조건문을 통과시키면서 처리한다.

package bj;
 
import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class p3055 {
    static int R,C;
    static char arr[][];
    static int moveX[] = {0,1,0,-1};
    static int moveY[] = {-1,0,1,0};
    static int map[][];
    static Point start,Destination;
    static Queue<Point> river = new LinkedList<>();
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        
        arr = new char[R][C];
        map = new int[R][C];
        for(int i=0; i<R; i++) {
            String str = br.readLine();
            for(int j=0; j<C; j++) {
                arr[i][j] = str.charAt(j);
                if(arr[i][j] == 'S')
                    start = new Point(j,i);
                else if(arr[i][j] =='*')
                    river.add(new Point(j,i));
                else if(arr[i][j] == 'D')
                    Destination = new Point(j,i);
            }
        }
        
        bfs(start);
//        for(int i=0; i<R; i++) {
//            for(int j=0; j<C; j++) {
//                System.out.print(map[i][j]+" ");
//            }System.out.println();
//        }
        if(map[Destination.y][Destination.x]==0) {
            System.out.println("KAKTUS");
        }else {
            System.out.println(map[Destination.y][Destination.x]-1);
        }
        
    }
    
    public static void bfs(Point p) {
        Queue<Point> queue = new LinkedList<>();
        map[p.y][p.x] = 1;
        queue.add(new Point(p.x, p.y));
        
        while(!queue.isEmpty()) {
            int currentRiver = river.size();
            
            for(int i=0; i<currentRiver; i++) {
                Point tmp = river.poll();
                int currentY = tmp.y;
                int currentX = tmp.x;
                
                for(int d=0; d<4; d++) {
                    int newY = currentY + moveY[d];
                    int newX = currentX + moveX[d];
                    
                    if(0<=newY && newY<R && 0<=newX && newX<C) {
                        if(arr[newY][newX]=='.') {
                            arr[newY][newX]='*';
                            river.add(new Point(newX,newY));
                        }
                    }
                }
            }
            
            int current = queue.size();
            for(int i=0; i<current; i++) {
                Point tmp = queue.poll();
                int y = tmp.y;
                int x = tmp.x;
                for(int d=0; d<4; d++) {
                    int newY = y + moveY[d];
                    int newX = x + moveX[d];
                    
                    if(0<=newY && newY<R && 0<=newX && newX<C) {
                        if(arr[newY][newX]!='*' && arr[newY][newX] !='X' && map[newY][newX]==0) {
                            map[newY][newX] = map[y][x] + 1;
                            queue.add(new Point(newX,newY));
                        }
                    }
                }
            }
            
        }
    }
    
}