【题解】【BFS】走出迷宫

#include<bits/stdc++.h>
using namespace std;
int x,nx,a[105][105],k=0,sx,sy,ex,ey;
int n,m;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
char s[105][105];

struct node{
	int x;
	int y;
	int step;
};

void bfs(int x,int y){

	queue<node>q;
	node n1;
	n1.x=x;
	n1.y=y;
	n1.step=0;
	//初始化队列状态 
	q.push(n1);
	while(!q.empty()){//当头指针值大于尾指针，说明所有节点搜索完毕
		//取对手的第一个元素进行搜索
		node tx=q.front(); 
		for(int i=0;i<4;i++){//方案数
			int nx=tx.x+dx[i];
			int ny=tx.y+dy[i]; 
			int step=tx.step;
			if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&s[nx][ny]!='#'&&!a[nx][ny]){//方案可行性 
				node ttx;
				ttx.x=nx;
				ttx.y=ny;
				ttx.step=step+1;
				a[nx][ny]=1;
				q.push(ttx);//入队操作 
				//记录新节点信息 
					if(ex==nx&&ey==ny){//找到目标 
						cout<<ttx.step<<endl;
					return ;
				}
			}
		}
		q.pop();//当前节点已经搜索完毕，进下一节点     出队操作 
	}
}
int main(){

	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>s[i][j];
			if(s[i][j]=='S'){
				sx=i,sy=j;
			} 
			if(s[i][j]=='T'){
				ex=i,ey=j;
			} 
		}
	}
	a[sx][sy]=1;
	bfs(sx,sy);
	 
	return 0; 
}

//与营救巨轮基本一致
#include<bits/stdc++.h>
#define N 1001
using namespace std;
struct node{
	int x,y,step;
}a,nf,nw;//a左上角 nf 队首，nw下一个入队的结点 
char maze[N][N];
int used[N][N];
int fx[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
int n,m,sx,sy,ex,ey;
queue<node>que;//队列
void bfs(){
	//先将a入队
	a.x=sx;
	a.y=sy;
	a.step=0; 
	used[a.x][a.y]=1;//能否删除 
	que.push(a);
	//只要队列不为空，遍历队列
	while(!que.empty()){
		//取出队首元素
		nf=que.front();
		
		if(nf.x==ex&&nf.y==ey) {
			cout<<nf.step<<endl;
			return ;
		}
		for(int i=0;i<4;i++){
			int nx=nf.x+fx[i][0];
			int ny=nf.y+fx[i][1];
			//长if 判断nx ny是否符合要求
			if(nx>=0&&nx<n&&ny>=0&&ny<m&&maze[nx][ny]=='.'&&!used[nx][ny]) {
				//符合要求的入队
				 nw.x=nx;
				 nw.y=ny;
				 nw.step=nf.step+1;
				 que.push(nw);
				 used[nx][ny]=1; 
			}	 
		}
		que.pop();//出队 
	} 
} 
int main(){
	cin>>n>>m;
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++){
			cin>>maze[i][j];
			if(maze[i][j]=='S'){
				sx=i;
				sy=j;
			}
			if(maze[i][j]=='T'){
				ex=i;
				ey=j;
				maze[i][j]='.';
			}
		}
	bfs();
	return 0;
}