94求调……
查看原帖
94求调……
741314
signed_long_long楼主2024/10/11 18:26

刚调完,94……

#include<bits/stdc++.h>
//------------------------------//
using namespace std;
int n,m,sx,sy; 
char a[305][305];
int z[30][3],w[30][3];
int dx[]={0,0,-1,1},dy[]={-1,1,0,0};
bool vis[505][505];
struct node{
	int x,y,st;
	bool flag=false; 
};
queue<node>s;
signed main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
			if(a[i][j]=='@') sx=i,sy=j;
			if(a[i][j]<='Z' and a[i][j]>='A'){
				int q=a[i][j]-'A'+1;
				z[q][z[q][2]++]=i;
				w[q][w[q][2]++]=j;
//				printf("%d %d %d\n",w[q][2],z[q][z[q][2]-1],w[q][w[q][2]-1]);
			}
		}
	}
//	return 0;
	s.push({sx,sy,0,false});
	while(s.size()){
		int x=s.front().x,y=s.front().y,st=s.front().st;
		bool flag=s.front().flag;
		s.pop();
//		printf("%d %d %d\n",x,y,st);
		if(vis[x][y]==true and a[x][y]=='.') continue;
		vis[x][y]=true;
	//	Sleep(100);
		if(x<1 or x>n or y<1 or y>m or a[x][y]=='#'){
			continue;
		}
		if(z[a[x][y]-'A'+1][2]>=2 and a[x][y]<='Z' and a[x][y]>='A' and flag==false){
			int u=a[x][y]-'A'+1;
			if(z[u][0]==x and w[u][0]==y){
				s.push({z[u][1],w[u][1],st,true});
			}else{
				s.push({z[u][0],w[u][0],st,true});
			}
			continue;
		}
		if(a[x][y]=='='){
			printf("%d",st);
			return 0;
		}
		for(int i=0;i<=3;i++){
			int nx=x+dx[i],ny=y+dy[i];
			if(!(nx<1 or nx>n or ny<1 or ny>m or a[nx][ny]=='#'))s.push({nx,ny,st+1,false});
		}
		
	}
//	for(int i=1;i<=n;i++){
//		for(int j=1;j<=m;j++){
//			cout<<a[i][j];
//			if(vis[i][j]) printf("1");
//			else printf("0");
//		}
//		printf("\n");
//	}
	return 0; 
}
2024/10/11 18:26
加载中...