吴添添 • 2年前
using namespace std; struct node{
int x,y;
int step;
};
char a[101][101]; int vis[105][105]; int n,m; int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}}; int sx,sy,ex,ey; void bfs() {
queue<node> qe;
node q,t;
q.x=sx,q.y=sy,q.step=0;
vis[q.x][q.y]=1;
qe.push(q);
while(!qe.empty())
{
q=qe.front();
qe.pop();
if(q.x==ex&&q.y==ey)
{
cout<<q.step;
break;
}
for(int i=0;i<4;i++)
{
t.x=q.x+dir[i][0];
t.y=q.y+dir[i][1];
if(a[t.x][t.y]=='.'&&vis[t.x][t.y]==0&&t.x>=1&&t.x<=n&&t.y>=1&&t.y<=n)
{
vis[t.x][t.y]=1;
t.step=q.step+1;
qe.push(t);
}
}
}
} int main() {
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>a[i][j];
if(a[i][j]=='S')
{
sx=i;
sy=j;
}
if(a[i][j]=='T')
{
ex=i;
ey=j;
a[i][j]='.';
}
}
}
bfs();
return 0; }
评论: