#P1033. 迷宫问题

发布时间 2023-11-25 20:22:30作者: yufan1102

题意是:

给你一个迷宫,起点为S,终点为T,.表示空格,#表示障碍物无法通过,你每次可以从当前位置上下左右移动(不能出界或者撞到障碍物上)你需要找出从起点到终点的最少步数,如果不存在解,输出-1。

BFS的练手题

using namespace std;
int sx,sy,ex,ey;
int n,m;
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
char mp[20][20];
int vis[20][20];
struct node{;
	int x,y,t;
	node(){};
	node(int a,int b,int c){
		x=a;
		y=b;
		t=c;
	}
};
bool BFS(){
    queue<node>q;
	q.push(node(sx,sy,0));
	vis[sx][sy]=1;
	while(q.size()){
		node u=q.front();
		q.pop();
		int x=u.x;
		int y=u.y;
		if(x==ex&&y==ey){
			cout<<u.t;
			return true;
		}
		for(int i=0;i<4;i++){
			int nx=x+dx[i];
			int ny=y+dy[i];
			if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&vis[nx][ny]==0&&mp[nx][ny]!='#'){
				vis[nx][ny]=1;
				q.push(node(nx,ny,u.t+1));
			}
		}
	}
	return false;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>mp[i][j];
			if(mp[i][j]=='S'){
				sx=i;
				sy=j;
			}
			if(mp[i][j]=='T'){
				ex=i;
				ey=j;
			}
		}
	}
	if(!BFS()){
		cout<<-1;
	}
	return 0;
}