40求调
查看原帖
40求调
793625
Pink_Cut_Tree楼主2023/7/30 20:51

码风良好+注释

// C++14 (GCC 9) -O2 by Present_Coming_Time(793625)
#include<bits/stdc++.h>
using namespace std; 
struct Node{
	int x,y,step; //step是步数 
}start,u;
int n,m,dx[4]={0,-1,0,1},dy[4]={1,0,-1,0},fx,fy;
char maze[305][305]; //地图 
bool vis[305][305],flag;
queue<Node>Q;
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>maze[i][j];
			if(maze[i][j]=='@'){
				start.x=i,start.y=j;
			}
			else if(maze[i][j]=='='){
				fx=i,fy=j;
			}
			else if(maze[i][j]=='#'){
				vis[i][j]=1;
			}
		}
	}
	vis[start.x][start.y]=1;
	Q.push(start);
	while(!Q.empty()){
		u=Q.front();
		Q.pop();
		//cout<<u.x<<" "<<u.y<<" "<<u.step<<"\n";
		if(u.x==fx&&u.y==fy){
			cout<<u.step; return 0; //直接输出 
		}
		for(int i=0;i<4;i++){
			int px=u.x+dx[i],py=u.y+dy[i]; //分离 
			if(px<1||px>n||py<1||py>m||vis[px][py]){ //判断越界 
				continue;
			}
			if('A'<=maze[px][py]&&maze[px][py]<='Z'){ //传送门 
				flag=0;
				for(int j=1;j<=n;j++){ //二重循环找 
					for(int k=1;k<=m;k++){
						if(maze[j][k]==maze[px][py]&&j!=px&&k!=py){ //保证不是原传送门 
							start.x=j,start.y=k,start.step=u.step+1; flag=1;break;
						}
					}
					if(flag==1){ //压缩时间 
						break;
					}
				}
				vis[start.x][start.y]=1; //打标记 
				Q.push(start); //入队 
			}
			else{
				start.x=px,start.y=py,start.step=u.step+1;
				vis[px][py]=1;
				Q.push(start);
			}
			
		}
	}
return 0;	
}
2023/7/30 20:51
加载中...