P1825 86pts求助
查看原帖
P1825 86pts求助
877271
legolas7楼主2023/9/4 17:37
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
long long n,m,que[3][9005],arr[905][905],head=1,tail=1,startx,starty;
char maze[905][905],str[905];
long long portal[105][105],fx[105]={-1,0,1,0},fy[105]={0,1,0,-1};
int main(){
	scanf("%lld %lld",&n,&m);
	fill(portal[0],portal[0]+4*105,-1);
	for(int i=0;i<n;i++){
		cin>>str;
		for(int j=0;j<m;j++){
			if(str[j]>='A'&&str[j]<='Z'){
				int let=str[j]-'A'+1;
				if(portal[0][let]==-1){
					portal[0][let]=i;
					portal[1][let]=j;
				}
				else{
					portal[2][let]=i;
					portal[3][let]=j;
				}
			}
			if(str[j]=='@'){
				startx=i;
				starty=j;
			}
			maze[i][j]=str[j];
		}
	}
	for(int i=1;i<=26;i++){
		if(portal[2][i]==-1&&portal[0][i]!=-1&&portal[1][i]!=-1){
			maze[portal[0][i]][portal[1][i]]='.';
		}
	}
	que[0][head]=startx;
	que[1][head]=starty;
	while(head<=tail){
        if(maze[startx][starty]=='='){
			printf("%lld",que[2][head]);
			exit(0);
		}
		for(int i=0;i<=3;i++){
			long long a=que[0][head]+fx[i],b=que[1][head]+fy[i];
			if(a>=0&&b>=0&&a<n&&b<m){
				if(maze[a][b]!='#'&&arr[a][b]==0){
					if(maze[a][b]>='A'&&maze[a][b]<='Z'){
						int lt=maze[a][b]-'A'+1;
						if(portal[0][lt]==a&&portal[1][lt]==b){
							a=portal[2][lt];
							b=portal[3][lt];
						}
						else{
							a=portal[0][lt];
							b=portal[1][lt];
						}
					}
					if(maze[a][b]=='='){
						printf("%lld",que[2][head]+1);
						exit(0);
					}
					tail++;
					arr[a][b]=1;
					if(maze[a][b]>='A'&&maze[a][b]<='Z') arr[a][b]=0;
					que[0][tail]=a;
					que[1][tail]=b;
					que[2][tail]=que[2][head]+1;
				}
			}
		}
		head++;
	}
	return 0;
}
2023/9/4 17:37
加载中...