39分bfs求助
查看原帖
39分bfs求助
831458
ChenHyz楼主2023/2/24 14:32
#include <bits/stdc++.h>
using namespace std;
struct node{int x,y,step;}t;
queue<node> q;
int n,m,vis[310][310];
char a[310][310];
int xy[][2]={{1,0},{0,1},{-1,0},{0,-1}};//方向数组 
bool check(int x,int y){
	if(x<1||y<1||x>n||y>m) return 0;
	return 1;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(a[i][j]=='@'){
				vis[i][j]=1;
				q.push((node){i,j,0});
				while(!q.empty()){
					int pos1,pos2;
					t=q.front();
					q.pop();
					if(a[t.x][t.y]=='=') break;
					for(int k=0;k<4;k++){
						int nx=t.x+xy[k][0];
						int ny=t.y+xy[k][1];
						if(check(nx,ny)&&!vis[nx][ny]&&a[nx][ny]>='A'&&a[nx][ny]<='Z'){//传送点 
							char ch=a[nx][ny];
							for(int i1=1;i1<=n;i1++){
								for(int j1=1;j1<=m;j1++){
									if(a[i1][j1]==ch&&i1!=nx&&j1!=ny){
										pos1=i1;pos2=j1;
									}
								}
							}
							vis[nx][ny]=1;vis[pos1][pos2]=1;
							q.push((node){pos1,pos2,t.step+1});
						}
						if(check(nx,ny)&&!vis[nx][ny]&&(a[nx][ny]=='.'||a[nx][ny]=='=')){//正常情况 
								vis[nx][ny]=1;
								q.push((node){nx,ny,t.step+1});
							}
					}
				}
			}
		}
	}
	cout<<t.step<<endl;
	return 0;
}
2023/2/24 14:32
加载中...