救救孩子吧,bfs 39pts,a了135789
查看原帖
救救孩子吧,bfs 39pts,a了135789
1070224
sc6666f楼主2024/7/20 21:24

实在是不知道那个传送门传过去之后又能回来再走的效果该怎么实现了

#include <bits/stdc++.h>
using namespace std;
int n,m;
int xs,ys,xe,ye;
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
char mp[500][500],vis[500][500];
struct node{
	int x,y,step;
};
struct pl{
	int i1=-1,j1=-1,i2,j2;
}ps[200];

queue <node> q;
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]=='@'){
				xs=i;
				ys=j;
			}if(mp[i][j]=='='){
				xe=i;
				ye=j;
			}if(mp[i][j]>='A' && mp[i][j]<='Z'){
				char c=mp[i][j];
				if(ps[c].i1==-1){
					ps[c].i1=i;
					ps[c].j1=j;
				}else {
					ps[c].i2=i;
					ps[c].j2=j;
				}
			}
		}
	}
	
	node st;
	st.x=xs;
	st.y=ys;
	st.step=0;
	q.push(st);
	vis[xs][ys]=1;
	while(!q.empty()){
		node s=q.front();
		q.pop();
		//cout<<s.x<<' '<<s.y<<' '<<s.step<<endl;
		if(mp[s.x][s.y]<='Z' && mp[s.x][s.y]>='A'){//判断传送门
			char nowc=mp[s.x][s.y];
			if(ps[nowc].i1==s.x && ps[nowc].j1==s.y)
			{
				if(vis[ps[nowc].i2][ps[nowc].j2]==0){
					node news;
					news.x=ps[nowc].i2;
					news.y=ps[nowc].j2;
					news.step=s.step+1;
					vis[news.x][news.y]=1; 
					q.push(news);
				}else{
					int nx,ny;
					for(int i=0;i<4;i++){
						nx=s.x+dx[i];
						ny=s.y+dy[i];
						if(nx>=1 && nx<=n && ny>=1 && ny<=m && vis[nx][ny]==0 && mp[nx][ny]!='#'){
							vis[nx][ny]=1;
							node newn;
							newn.x=nx;
							newn.y=ny;
							newn.step=s.step+1;
							q.push(newn);
						}
					}
				}
			}
			else
			{
				if(vis[ps[nowc].i1][ps[nowc].j1]==0){
					node news;
					news.x=ps[nowc].i1;
					news.y=ps[nowc].j1;
					news.step=s.step;
					vis[news.x][news.y]=1; 
					q.push(news);
				}else{
					int nx,ny;
					for(int i=0;i<4;i++){
						nx=s.x+dx[i];
						ny=s.y+dy[i];
						if(nx>=1 && nx<=n && ny>=1 && ny<=m && vis[nx][ny]==0 && mp[nx][ny]!='#'){
							vis[nx][ny]=1;
							node newn;
							newn.x=nx;
							newn.y=ny;
							newn.step=s.step+1;
							q.push(newn);
						}
					}
				}
			}
			vis[s.x][s.y]=0;
			continue;
		}//--------------------------上面是判断传送门 
		if(s.x==xe && s.y==ye){
			cout<<s.step;
			return 0;
		}//--------------------------上面是终点 
		if(mp[s.x][s.y]=='.' || mp[s.x][s.y]=='@'){
			int nx,ny;
			for(int i=0;i<4;i++){
				nx=s.x+dx[i];
				ny=s.y+dy[i];
				if(nx>=1 && nx<=n && ny>=1 && ny<=m && vis[nx][ny]==0 && mp[nx][ny]!='#'){
					vis[nx][ny]=1;
					node newn;
					newn.x=nx;
					newn.y=ny;
					newn.step=s.step+1;
					q.push(newn);
				}
			}
		}//----------------------------上面是正常草地
	}
	cout<<-1;
	return 0;
}
2024/7/20 21:24
加载中...