93分,第7点的wa了,求救
查看原帖
93分,第7点的wa了,求救
709586
lllllluogu楼主2024/3/29 13:55
#include <bits/stdc++.h>
using namespace std;
int ans,n,m,vis[305][305],f[305][305];
int dx[]={1,0,-1,0},dy[]={0,1,0,-1};
struct node{int x;int y;}S,T;
struct to{node n1;node n2;}to[30];
char s[305][305];
void bfs(){
	queue<node>q;
	q.push((node){S.x,S.y});
	vis[S.x][S.y]=1;f[S.x][S.y]=0;
	while(!q.empty()){
		node cur=q.front();q.pop();
		int tmp=f[cur.x][cur.y];
		for(int i=0;i<4;i++){
			int tx=cur.x+dx[i],ty=cur.y+dy[i];
			if(tx<=0||tx>n||ty<=0||ty>m||vis[tx][ty]||s[tx][ty]=='#')continue;
			if(tx==T.x&&ty==T.y){
				cout<<tmp+1;return ;
			}
			if(s[tx][ty]=='.'){
				vis[tx][ty]=1;f[tx][ty]=tmp+1;q.push((node){tx,ty});
			}
			else if(s[tx][ty]>='A'&&s[tx][ty]<='Z'){
				int t=s[tx][ty]-'A'+1;
				if(tx==to[t].n1.x&&ty==to[t].n1.y)
					f[to[t].n2.x][to[t].n2.y]=tmp+1,q.push((node){to[t].n2.x,to[t].n2.y});
				else
					f[to[t].n1.x][to[t].n1.y]=tmp+1,q.push((node){to[t].n1.x,to[t].n1.y});
			}
		}
	}
}
int main(){
	cin>>n>>m;int x,y;
	for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++){
		cin>>s[i][j];
		if(s[i][j]=='@')S.x=i,S.y=j;
		if(s[i][j]=='=')T.x=i,T.y=j;
		if(s[i][j]>='A'&&s[i][j]<='Z'){
			int t=s[i][j]-'A'+1;
			if(!to[t].n1.x&&!to[t].n1.y)to[t].n1.x=i,to[t].n1.y=j;
			else to[t].n2.x=i,to[t].n2.y=j;
		}
	}
	bfs();	
}

2024/3/29 13:55
加载中...