include
include
include
include
using namespace std;
int w[100][100], p[100][100];
char a[100][100];
int main()
{
int n, m, l, i, j, k, sx, sy, ex, ey, fx, fy;
scanf ("%d %d",&m,&n);
queue x;
queue y;
for (i=0; i {
scanf ("%s",a[i]);
for (j=0; j {
w[i][j]=-1; p[i][j]=-1;
if (a[i][j]=='S')
{
sx=i;
sy=j;
a[i][j]='.';
}
else if (a[i][j]=='*')
{
x.push(i);
y.push(j);
w[i][j]=0;
a[i][j]='.';
}
else if (a[i][j]=='D')
{
ex=i;
ey=j;
w[i][j]=999999999;
a[i][j]='.';
}
else
{
p[i][j]=-2;
w[i][j]=-2;
}
}
}
k=0;
while (!x.empty())
{
l=x.size();
k+=1;
for (i=0; i {
fx=x.front(); fy=y.front();
x.pop(); y.pop();
if (fx-1>=0)
{
if (w[fx-1][fy]==-1)
{
x.push(fx-1); y.push(fy);
w[fx-1][fy]=k;
}
}
if (fx+1 {
if (w[fx+1][fy]==-1)
{
x.push(fx+1); y.push(fy);
w[fx+1][fy]=k;
}
}
if (fy-1>=0)
{
if (w[fx][fy-1]==-1)
{
x.push(fx); y.push(fy-1);
w[fx][fy-1]=k;
}
}
if (fy+1 {
if (w[fx][fy+1]==-1)
{
x.push(fx); y.push(fy+1);
w[fx][fy+1]=k;
}
}
}
}
x.push(sx); y.push(sy);
p[sx][sy]=0;
k=0;
while (!x.empty())
{
l=x.size();
k+=1;
for (i=0; i {
fx=x.front(); fy=y.front();
x.pop(); y.pop();
if (fx-1>=0)
{
if ((p[fx-1][fy]==-1)&&(w[fx-1][fy]>k))
{
x.push(fx-1); y.push(fy);
p[fx-1][fy]=k;
}
}
if (fx+1 {
if ((p[fx+1][fy]==-1)&&(w[fx+1][fy]>k))
{
x.push(fx+1); y.push(fy);
p[fx+1][fy]=k;
}
}
if (fy-1>=0)
{
if ((p[fx][fy-1]==-1)&&(w[fx][fy-1]>k))
{
x.push(fx); y.push(fy-1);
p[fx][fy-1]=k;
}
}
if (fy+1 {
if ((p[fx][fy+1]==-1)&&(w[fx][fy+1]>k))
{
x.push(fx); y.push(fy+1);
p[fx][fy+1]=k;
}
}
}
}
if (p[ex][ey]==-1)
printf ("KAKTUS\n");
else
printf ("%d\n",p[ex][ey]);
return 0;
}
can someone please help..