[ Baekjoon ] No.3055 탈출

import java.io.*;
import java.util.*;

public class Main {
	static int R,C;
	static char[][] map;
	static int[][] map2;
	static int[][] dir = // 네방향
	static boolean check(int x, int y) {
		if(x>=0 && x<R && y>=0 && y<C) {
			return true;
		} else return false;
	}
	
	
	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());
		map = new char[R][C];
		map2= new int[R][C];
		pos res = null;
		for(int i=0; i<R; i++) {
			String tmp = br.readLine().trim();
			for(int j=0; j<C; j++) {
				map[i][j] = tmp.charAt(j);
				if(map[i][j]=='*') quW.add(new pos(i,j));
				else if(map[i][j]=='S') {
					quS.add(new pos(i,j));
				}else if(map[i][j]=='D') {
					res = new pos(i,j);
				}
			}
		}
		solution();
		System.out.println(map2[res.x][res.y]==0 ? "KAKTUS" : map2[res.x][res.y]);
	}
	static LinkedList<pos> quW = new LinkedList<>();
	static LinkedList<pos> quS = new LinkedList<>();
	static void solution() {
		while(!quS.isEmpty()) {
			int size = quS.size();
			extendsWater();
			for(int i=0; i<size; i++) {
				pos p = quS.poll();
				for(int d=0; d<4; d++) {
					int dx = p.x + dir[d][0];
					int dy = p.y + dir[d][1];
					if(check(dx,dy) && (map[dx][dy]=='.' || map[dx][dy]=='D')){
						map[dx][dy]='S';
						map2[dx][dy]=map2[p.x][p.y]+1;
						quS.add(new pos(dx,dy));
					}
				}
			}
		}
	}

	static void extendsWater() {
		int size = quW.size();
		for(int i=0; i<size; i++) {
			pos p = quW.poll();
			for(int d=0; d<4; d++) {
				int dx = p.x + dir[d][0];
				int dy = p.y + dir[d][1];
				if(check(dx,dy) && map[dx][dy]=='.') {
					map[dx][dy]='*';
					quW.add(new pos(dx,dy));
				}
			}
		}
	}
	
	static class pos{
		int x,y;

		public pos(int x, int y) {
			this.x = x;
			this.y = y;
		}

		@Override
		public String toString() {
			return "pos [x=" + x + ", y=" + y + "]";
		}
		
	}
}