Slikar

/*
    Task    : _example
    Author  : Phumipat C. [MAGCARI]
    Language: C++
    Created : 07 November 2022 [20:39]
*/
#include<bits/stdc++.h>
using namespace std;
struct A{
    int i,j,state,type;
};
queue<A > que;
char a[55][55];
int dir[2][4] = {{1,-1,0,0},{0,0,1,-1}};
int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);
    int r,c,sti,stj,eni,enj;
    cin >> r >> c;
    for(int i=1;i<=r;i++){
        for(int j=1;j<=c;j++){
            cin >> a[i][j];
            if(a[i][j] == 'S')
                sti = i,stj = j;
            else if(a[i][j] == 'D')
                eni = i,enj = j;
            else if(a[i][j] == '*')
                que.push({i,j,0,1});
        }
    }
    que.push({sti,stj,0,0});
    while(!que.empty()){
        A now = que.front();
        que.pop();
        if(now.type == 0 && now.i == eni && now.j == enj){
            cout << now.state << '\n';
            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' || a[ni][nj] == '*')    continue;
            if(now.type == 1 && a[ni][nj] == 'D')       continue;
            a[ni][nj] = '*';
            que.push({ni,nj,now.state+1,now.type});
        }
    }
    cout << "KAKTUS\n";
    return 0;
}