0分求助!过不了样例!
查看原帖
0分求助!过不了样例!
217023
Melody2009楼主2023/8/10 23:27
#include<cstdio>
#include<iostream>
#include<queue>
#include<map>
using namespace std;
int n,m;
char a[302][302],u[302][302],sp[302][302];
int xx[4]={0,1,0,-1},yy[4]={1,0,-1,0};
struct p1825
{
	int x1,x2,y1,y2,flag;
};
map<char,p1825> cs;
int x,y;
struct node
{
	int x,y,s;
};
queue<node> q;
void bfs()
{
	node k;k.x=x;k.y=y;k.s=0;
	q.push(k);
	while(!q.empty())
	{
		node h=q.front();
		for(int i=0;i<4;i++)
		{
			int tx=h.x+xx[i],ty=h.y+yy[i];
			if(a[tx][ty]=='=')
			{
				cout<<h.s+1<<endl;exit(0);
			}
			else
				if(a[tx][ty]>='A'&&a[tx][ty]<='Z'&&sp[tx][ty]!='#')
				{
					if(cs[a[tx][ty]].flag==1)
					{
						sp[tx][ty]='#';k.x=tx;k.y=ty,k.s=h.s+1;
						q.push(k);
						continue;
					}
					sp[tx][ty]='#';
					char flag2=a[tx][ty];
					if(cs[flag2].x1==tx&&cs[flag2].y1==ty)
					{
						tx=cs[flag2].x2;
						ty=cs[flag2].y2;
					}
					else
					{
						tx=cs[flag2].x1;
						ty=cs[flag2].y1;
					}
					k.x=tx,k.y=ty,k.s=h.s+1;
					q.push(k);
				}
				else
					if(a[tx][ty]=='.'&&u[tx][ty]=='.')
					{
						u[tx][ty]='#';k.x=tx,k.y=ty,k.s=h.s+1;
						q.push(k);
					}
			q.pop();
		}
	}
}
int main()
{
	freopen("p1825.in","r",stdin);
	freopen("p1825.out","w",stdout);
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			cin>>a[i][j];
			sp[i][j]=a[i][j];
			u[i][j]=a[i][j];
			if(a[i][j]>='A'&&a[i][j]<='Z')
			{
				if(cs[a[i][j]].flag==0)
				{
					cs[a[i][j]].x1=i;
					cs[a[i][j]].y1=j;
					cs[a[i][j]].flag++;
				}
				else
				{
					cs[a[i][j]].x2=i;
					cs[a[i][j]].y2=j;
					cs[a[i][j]].flag++;
				}
				sp[i][j]=a[i][j];
			}
			else
				if(a[i][j]=='@') x=i,y=j;
		}
	bfs();
	return 0;
}

2023/8/10 23:27
加载中...