悬赏关注
查看原帖
悬赏关注
511520
drmr楼主2022/11/16 20:23

emo,57分

#include <bits/stdc++.h>
using namespace std;
int n,m;
struct point{
	int x,y,step;
}a[1000][1000];
point s;
char b[1000][1000];
point q[10000000];
int front,tail;
int used[1000][1000];
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
point tel_1[200];
point tel_2[200];
int main(){
	scanf("%d%d",&n,&m);
	for(int i = 0;i<n;i++){
		scanf("%s",b[i]);
		for(int j = 0;j<m;j++){
			if(b[i][j] == '@'){
				s.x = i,s.y = j;
				s.step = 0;
			}
			else if(b[i][j]>='A' && b[i][j]<='Z'){
				if(tel_1[b[i][j]].step == 0){
					tel_1[b[i][j]].x = i;
					tel_1[b[i][j]].y = j;
					tel_1[b[i][j]].step = 1;
				}
				else{
					tel_2[b[i][j]].x = i;
					tel_2[b[i][j]].y = j;
				}
			}
		}
	}
	front = tail = 1;
	q[1]=s;
	used[s.x][s.y]=1;
	while(front<=tail){
		point u=q[front++];
		point v;
		for(int i=0;i<4;i++){
			v.x = u.x + dx[i];
			v.y = u.y + dy[i];
			v.step = u.step + 1;
			if(v.x<0 || v.y<0 || v.x>=n || v.y>=n) continue;
			if(b[v.x][v.y] == '#') continue;
			if(used[v.x][v.y] == 1) continue;
			
			int flag=0;
			if(b[v.x][v.y]>='A' && b[v.x][v.y]<='Z'){
				if(tel_1[b[v.x][v.y]].x == v.x && tel_1[b[v.x][v.y]].y == v.y){
					int k=v.step;
					v = tel_2[b[v.x][v.y]];
					v.step=k;
				}
				else{
					int k=v.step;
					v = tel_1[b[v.x][v.y]];
					v.step=k;
				}
				flag=1;
			}
			
			q[++tail] = v;
			if(flag==0) used[v.x][v.y] = 1;
			if(b[v.x][v.y] == '='){
				cout<<v.step<<endl;
				return 0;
			}
		}
	}
	return 0;
}
2022/11/16 20:23
加载中...