fdsshy

吴添添  •  2年前


include<bits/stdc++.h>

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; }


评论: