Slikar

/*
    Task    : ฺBreadth First Search
    Author  : Phumipat C. [MAGCARI]
    Language: C++
    Created : 10 October 2022 [21:04]
*/
#include<bits/stdc++.h>
using namespace std;
struct A{
    int i,j,type;
};
int dir[2][4] = {{1,0,-1,0},{0,1,0,-1}};
char a[55][55];
queue<A > que;
int dis[55][55];
int main(){
    int r,c,sti,stj,eni,enj;
    scanf("%d %d",&r,&c);
    for(int i=1;i<=r;i++){
        scanf(" %s",a[i]+1);
        for(int j=1;j<=c;j++){
            if(a[i][j] == 'S'){
                sti = i,stj = j;
                a[i][j] = '.';
            }else if(a[i][j] == 'D'){
                eni = i,enj = j;
                a[i][j] = '.';
            }else if(a[i][j] == '*'){
                que.push({i,j,1});
                a[i][j] = 'X';
            }
            dis[i][j] = 1e9;
        }
    }
    que.push({sti,stj,0});
    dis[sti][stj] = 0;
    while(!que.empty()){
        A now = que.front();
        que.pop();
        if(now.i == eni && now.j == enj){
            printf("%d\n",dis[now.i][now.j]);
            return 0;
        }
        for(int k=0;k<4;k++){
            int ni = now.i+dir[0][k],nj = now.j+dir[1][k];
            if(ni<1 || nj<1 || ni>r || nj>c)    continue;
            if(a[ni][nj] == 'X')                continue;
            if(now.type == 0){
                if(dis[ni][nj] != 1e9)          continue;
                dis[ni][nj] = dis[now.i][now.j]+1;
                que.push({ni,nj,0});
            }else{
                if(ni == eni && nj == enj)      continue;
                a[ni][nj] = 'X';
                que.push({ni,nj,1});
            }
        }
    }
    printf("KAKTUS\n");
    return 0;
}