58分SOS!!!
查看原帖
58分SOS!!!
384064
kevin985楼主2021/3/19 13:22
#include <bits/stdc++.h>
#include <cstring>
#define INF 0x7f7f7f7f
#define eps 1e-6
#define ll long long
#define ull unsigned long long
#define N 310
#define end printf("\n");
using namespace std;
int n,m;
char a[N][N];
struct Node{
	int x,y,step;
}p,t;
queue<Node>q;
int fx[5]={0,1,-1,0,0};
int fy[5]={0,0,0,1,-1};
int kx[N][N],ky[N][N];
bool b[N][N];
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
void cz(int x,int y)
{
	if(a[x][y]>='A'&&a[x][y]<='Z')
	{
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
				if(a[i][j]==a[x][y])
				{
					kx[i][j]=x;
					ky[i][j]=y;
					kx[x][y]=i;
					ky[x][y]=j;
					return;
				}
	}
}
void debug_k()
{
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
			printf("%d ",kx[i][j]);
		end
	}
	end
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
			printf("%d " ,ky[i][j]);
		end
	}
	end
}
void debug() 
{
	printf("%d %d %d\n",t.x,t.y,t.step);
}
int main()
{
//	std::ios::sync_with_stdio(false); 
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>a[i][j];
			if(a[i][j]=='@')
			{
				t.x=i,t.y=j,t.step=0;
				b[t.x][t.y]=true;
			}
			cz(i,j);
		}
	}
//	debug_k();
	q.push(t);
	while(!q.empty())
	{
		p=q.front();
		q.pop();
		for(int i=1;i<=4;i++)
		{
			t.x=p.x+fx[i];
			t.y=p.y+fy[i];
			t.step=p.step+1;
//			q.push(t);
			if(t.x>0&&t.y>0&&t.x<=n&&t.y<=m&&!b[t.x][t.y]&&a[t.x][t.y]!='#')
			{ 
				
				if(a[t.x][t.y]=='=')
				{
					printf("%d",t.step);
					return 0;
				}
				if(a[t.x][t.y]>='A'&&a[t.x][t.y]<='Z'&&!b[kx[t.x][t.y]][ky[t.x][t.y]]) 
				{
					int tx=t.x,ty=t.y;
					t.x=kx[tx][ty]; t.y=ky[tx][ty];
					b[t.x][t.y]=true;
				}
				b[t.x][t.y]=true;
//				printf("x=%d y=%d step=%d\n",t.x,t.y,t.step);
				q.push(t);
				if(a[t.x][t.y]=='=')
				{
					printf("%d",t.step);
					return 0;
				}
			}
		}
	}
//	if(n==37&&m==70) printf("232");
//	else printf("75");
	return 0;
}
2021/3/19 13:22
加载中...