jiujiuwo
查看原帖
jiujiuwo
601277
code_404楼主2022/8/30 15:50
#include<bits/stdc++.h>
using namespace std;
const int maxn=400;
int n,m,bx,by,lx,ly,nnx,nny;
long long step[maxn][maxn];
char a[maxn][maxn];
struct node{
	int xx,yy;
	int zx,zy,zzx,zzy,ci;
}shu[maxn*maxn],word[maxn];
int fx[]={-1,0,1,0};
int fy[]={0,1,0,-1};
queue<node>q;
bool check(int x,int y){
	if(x<=0||y<=0||x>n||y>m)return 0;
	if(step[x][y]!=-1)return 0;
	return true;
}
bool check1(int x,int y){
	if(x<=0||y<=0||x>n||y>m)return 0;
	return true;
}
int main(){
	scanf("%d%d",&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]=='@')bx=i,by=j;
			if(a[i][j]=='=')lx=i,ly=j;
			if(a[i][j]<='Z'&&a[i][j]>='A'){
				int mm=a[i][j]-'A';
				if(word[mm].ci==0)word[mm].ci++,word[mm].zx=i,word[mm].zy=j;
				else word[mm].zzx=i,word[mm].zzy=j;
			}
		}
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)step[i][j]=-1;
		
	step[bx][by]=0;
	node tt;
	tt.xx=bx,tt.yy=by;
	q.push(tt);
	while(!q.empty()){
		node t=q.front();
		q.pop();
		for(int i=0;i<4;i++){
			node temp;
			int nx=t.xx+fx[i],ny=t.yy+fy[i];
			temp.xx=nx,temp.yy=ny;//where
			if(a[nx][ny]=='#')continue;
			else {			
				if(a[nx][ny]=='.'){
					if(check(nx,ny)){
						q.push(temp);
						step[nx][ny]=step[t.xx][t.yy]+1;
					}
				}
				else if(a[nx][ny]=='='){
					printf("%d",step[t.xx][t.yy]+1);
					return 0;
				}
				else {
					int ttt=a[nx][ny]-'A';
					if(word[ttt].zx!=nx||word[ttt].zy!=ny){
						nnx=word[ttt].zx,nny=word[ttt].zy;
						if(check1(nnx,nny)&&check1(nx,ny)){
							step[nx][ny]=step[t.xx][t.yy]+1;
							step[nnx][nny]=step[t.xx][t.yy]+1;
							temp.xx=nnx,temp.yy=nny;
							q.push(temp);
						}
					}
					else{
						nnx=word[ttt].zzx,nny=word[ttt].zzy;
						if(check1(nx,ny))step[nx][ny]=step[t.xx][t.yy]+1;
						if(check1(nnx,nny)){
							step[nnx][nny]=step[t.xx][t.yy]+1;
							temp.xx=nnx,temp.yy=nny;
							q.push(temp);
						}
					}
				}	
			}
		}	
	}
	return 0;
}
2022/8/30 15:50
加载中...