bfs,13分(有注释),求助,回报一关注
查看原帖
bfs,13分(有注释),求助,回报一关注
635829
D_FANG楼主2022/9/30 17:29
#include<bits/stdc++.h>
using namespace std;
int n,m,vis[310][310],a[310][310];
int st1,st2,en1,en2;
queue<int>q1;//x坐标 
queue<int>q2;//y坐标 
queue<int>q;//最小步数
int s1,s2;//记录传送点
int ans=999999999;//记录答案 
bool check(int x,int y){
	if (a[x][y]>='A'&&a[x][y]<='Z'){
		return true;
	}
	return false;
}//检查是否是传送点 
void finds(int x,int y){
	for (int i=1;i<=n;i++){
		for (int j=1;j<=m;j++){
			if (i!=x&&j!=y&&a[i][j]==a[x][y]){
				s1=i;
				s2=j;
				return ;
			}
		}
	}
}//寻找传送点 
int dx[5]={0,0,0,1,-1};//移动 
int dy[5]={0,1,-1,0,0};//移动 
void bfs(int b,int c){
	q.push(0);
	q1.push(b);
	q2.push(c);
	if (a[b][c]>='A'&&a[b][c]<='Z'){
		finds(b,c);
	}//检查初始坐标是否为传送点 
	vis[b][c]=1;//已走过地图 
	while (!q.empty()){
		int x=q1.front();
		int y=q2.front();
		int z=q.front();
		q.pop();
		q1.pop();
		q2.pop();
		for (int i=1;i<=4;i++){
			int xx=dx[i]+x;//下一步坐标 
			int yy=dy[i]+y;//同上 
			if (xx>0&&yy>0&&xx<=n&&yy<=m&&a[xx][yy]!=1&&vis[xx][yy]!=1){//判断是否可走 
				if (xx==en1&&yy==en1){//终点 
					ans=min(ans,z+1);
					continue; 
				}
				vis[xx][yy]=1;//标记已走过 
				if (!check(xx,yy)){
					q.push(z+1);
					q1.push(xx);
					q2.push(yy);
					continue;
				}
				else{
					finds(xx,yy);
					q.push(z+1);
					q1.push(s1);
					q2.push(s2);
					continue;
				}
			}
		}
	}
}
int main(){
	cin>>n>>m;
	for (int i=1;i<=n;i++){
		for (int j=1;j<=m;j++){
			char h;
			cin>>h;
			if (h=='.'){
				a[i][j]=1;//障碍 
			}
			if (h>='A'&&h<='Z'){
				a[i][j]=h;//传送点 
			}
			if (h=='@'){//起点 
				st1=i;
				st2=j;
			}
			if (h=='='){//终点 
				en1=i;
				en2=j;
			}
		}
	}
	bfs(st1,st2);
	cout<<ans;
	return 0;
}
2022/9/30 17:29
加载中...