#include<bits/stdc++.h>
#include<stdio.h>
using namespace std;
typedef struct xy{
int x,y;
char t;
}xy;
xy dest,start;
int R,C;
char ar[52][52]={0,};
int visited[52][52]={0,};
int water[52][52]={0,};
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
queue<xy> q;
void BFS(int y,int x){
q.push({x,y,'.'});
int flag=0;
while(!q.empty()){
int x=q.front().x;
int y=q.front().y;
int t=q.front().t;
q.pop();
for(int i=0;i<4;i++){
int nx=dx[i]+x;
int ny=dy[i]+y;
if(t=='*'){
// printf("water : (%d,%d) from (%d,%d)\n",ny,nx,y,x);
if(nx<0||nx>=C||ny<0||ny>=R)continue;
if(water[ny][nx]!=-1||ar[ny][nx]=='D'||ar[ny][nx]=='X')continue;
// printf("yes\n");
q.push({nx,ny,'*'});
water[ny][nx]=water[y][x]+1;
}else{
// printf("doch : (%d,%d)\n",ny,nx);
if(nx<0||nx>=C||ny<0||ny>=R)continue;
if(visited[ny][nx]!=-1||ar[ny][nx]=='X')continue;
// printf("yes\n");
if(water[ny][nx]<=visited[y][x]+1&&water[ny][nx]!=-1)continue;
visited[ny][nx]=visited[y][x]+1;
q.push({nx,ny,'.'});
if(ar[ny][nx]=='D'){
cout << visited[dest.y][dest.x] << endl;
flag=1;
}
}
}
}
if(!flag){
cout << "KAKTUS" << endl;
}
// for(int i=0;i<R;i++){
// for(int j=0;j<C;j++){
// printf("%2d",visited[i][j]);
// }puts("");
// }
}
int main(void){
scanf("%d %d",&R,&C);
memset(visited,-1,sizeof(visited));
memset(water,-1,sizeof(visited));
for(int i=0;i<R;i++){
for(int j=0;j<C;j++){
scanf("%1s",&ar[i][j]);
if(ar[i][j]=='D'){
dest.y=i;
dest.x=j;
}else if(ar[i][j]=='*'){
q.push({j,i,'*'});
water[i][j]++;
}else if(ar[i][j]=='S'){
ar[i][j]='.';
visited[i][j]++;
start.x=j;
start.y=i;
}
}
}
// for(int i=0;i<R;i++){
// for(int j=0;j<C;j++){
// printf("%c,",ar[i][j]);
// }
// puts("");
// }
BFS(start.y,start.x);
}비버의 집, 고슴도치의 시작 위치, 물이 차오를 곳을 입력받는다.
먼저, queue 에 물이 차오를 곳의 위치를 전부 push 한 뒤, 시작지점의 위치를 push 해야한다.
실수로 입력받을 때 시작지점의 위치를 push 해버려서 예제는 다 맞았는데 21% 에서 틀렸다.
왜냐하면, 고슴도치 시작위치 뒤에 물이 있으면, 물이 차오를 곳을 미리 표시하지 않았기 때문에
고슴도치가 이동하고 물이 이동해서 고슴도치가 죽어버린다.
일단 물 map, 고슴도치 map 을 -1 으로 초기화 한 뒤,
각각의 시작위치는 0으로 지정하고 다음으로 이동할 곳 4방향에 현재위치 + 1 을 넣는다.
그러면 시작위치에서 멀어질수록 숫자가 점점 증가하는 지도가 그려지는데,
이 때 물 map 상의 고슴도치가 이동할 곳의 숫자가 고슴도치 현재위치+1 과 같으면,
같은시간이지만 물이 이동할 곳에는 고슴도치가 못가고,
더 작으면 이미 물이 위치한 곳이기 떄문에 못가고,
더 커야 적어도 다음턴에는 물이 없기때문에 이동할 수 있다.
위 코드의 경우는 water[ny][nx]<=visited[y][x]+1 으로 continue 를 하는데,
물이 없는 곳 ( -1 으로 초기화 ) 에서도 만족하기 때문에 water[ny][x]!=-1 조건을 붙여줘야 한다.
