58分求调!
查看原帖
58分求调!
932822
zhongy楼主2023/2/12 18:11

https://www.luogu.com.cn/record/102030877

这是wa的点

#include <bits/stdc++.h>
using namespace std;
int dis[301][301];
char a[301][301];
int st[301][301];//能不能走! 
int n,m;
int fx,fy,sx,sy;//起点和终点 
int f1[26][2];
int f2[26][2];
int flag[26];
pair<int,int> q[100001];
void bfs()
{
	int front=1,rear=0;
	q[++rear]={sx,sy};
	st[sx][sy]=1;
	dis[sx][sy]=0;
	int tx[4]={0,1,0,-1};
	int ty[4]={1,0,-1,0};
	while(front<=rear)
	{
		auto t=q[front++];	
		for(int i=0;i<4;i++)
		{
			int x=t.first+tx[i],y=t.second+ty[i];
			if(!st[x][y]&&x<=n&&x>0&&y>0&&y<=m)
			{
				st[x][y]=1;
				if(a[x][y]-'a'>=0&&a[x][y]-'a'<26)
				{ 
				//	cout<<a[x][y]<<x<<y<<"    ";
					if(f1[a[x][y]-'a'][0]==x&&f1[a[x][y]-'a'][1]==y)
					{
					int tmp=a[x][y]-'a';
					x=f2[tmp][0];
					y=f2[tmp][1];
				//	cout<<f2[tmp][0]<<f2[tmp][1]<<"     ";
					}
					else {
					int tmp=a[x][y]-'a';
					x=f1[tmp][0];
					y=f1[tmp][1];
				//	cout<<f1[tmp][0]<<f1[tmp][1]<<"     ";
					}
				//	cout<<a[x][y]<<x<<y<<endl;
				}
			
				dis[x][y]=dis[t.first][t.second]+1;	
				if(x==fx&&y==fy) return;
				q[++rear]={x,y};
				st[x][y]=1;
			}
		}
	}
}
int main()
{
	cin>>n>>m;
	int i,j;
	for(i=1;i<=n;i++)
	for(j=1;j<=m;j++)
	{
		char c;
		scanf(" %c",&c);
		if(c=='#')
		st[i][j]=1;
		else if(c=='.')
		;
		else if(c=='=')
		fx=i,fy=j;
		else if(c=='@')	sx=i,sy=j;
		else {
			c=c+32;
			a[i][j]=c;
			if(!flag[c-'a']) 
			{
			f1[c-'a'][0]=i;f1[c-'a'][1]=j;flag[c-'a']=1;
			}else {
			f2[c-'a'][0]=i;f2[c-'a'][1]=j;
			}
		}
	}
	bfs();
	cout<<dis[fx][fy];
}
2023/2/12 18:11
加载中...