59玄关求调
查看原帖
59玄关求调
614672
ftzx楼主2024/9/27 20:43
#include<iostream>
#include<queue>
using namespace std;
const int N=305,dlt[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
int n,m,x1,y1,x2,y2,dis[N][N];
char maze[N][N];
struct Pos{
	int x, y;
} door[N];
inline bool check(int x,int y){
	return x>=1&&x<=n&&y>=1&&y<=m&&maze[x][y]!='#';
}
void bfs(){
	maze[x1][y1]='#';
	Pos u={x1,y1};
	queue<Pos> q;
	q.push(u);
	while(!q.empty()){
		u = q.front();q.pop();
		for(int i=0;i<4;i++){
			int dx=u.x+dlt[i][0],dy=u.y+dlt[i][1];
			if(check(dx,dy)){
				dis[dx][dy]=dis[u.x][u.y]+ 1;
				Pos v={dx,dy};
				if(maze[dx][dy]>='A'&&maze[dx][dy]<='Z'){
					if(door[maze[dx][dy]].x==dx&&door[maze[dx][dy]].y==dy){
						v.x=door[maze[dx][dy]+ 26].x;
						v.y=door[maze[dx][dy]+ 26].y;
					}
					else {
						v.x=door[maze[dx][dy]].x;
						v.y=door[maze[dx][dy]].y;
					}
					dis[v.x][v.y]=dis[dx][dy];
					maze[v.x][v.y]='#';
				}
				maze[dx][dy]='#';
				q.push(v);
			}
		}
	}
}
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]=='@')x1=i,y1=j;
			if(maze[i][j]=='=')x2=i,y2=j;
			if(maze[i][j]>='A'&&maze[i][j]<='Z')
			if(door[maze[i][j]].x==0){
				door[maze[i][j]].x=i;
				door[maze[i][j]].y=j;
			}
			else {
				door[maze[i][j]+26].x=i;
				door[maze[i][j]+26].y=j;
			}
		}
	bfs();
	cout << dis[x2][y2];
	return 0;
}

就很奇怪,半天没看懂

2024/9/27 20:43
加载中...