题目

提交记录

#include<bits/stdc++.h>
using namespace std;
int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1},xd[4]={-1,1,1,-1},yd[4]={-1,1,-1,1},s=1e6,n;
char a[1201][1201];
int v[1201][1201];
struct S{
	int x,y,step;
}s1;
queue<S>q;
void bfs(int a1,int a2)
{
	while(!q.empty())q.pop();
	memset(v,0,sizeof(v));
	q.push({a1,a2,1});
	v[a1][a2]=1;
	while(!q.empty())
	{
		 s1=q.front();
		 q.pop();
		 if(s1.x==n&&s1.y==n)s=min(s,s1.step);
		 if(a[s1.x][s1.y]=='A')
		 {
		    for(int i=0;i<4;i++)
		    {
		 	   int xx=s1.x+dx[i],yy=s1.y+dy[i];
		 	   if(xx>0&&yy>0&&xx<=n&&yy<=n&&v[xx][yy]==0&&a[xx][yy]!='*')
		 	   {
		 	   	 v[xx][yy]=1;
		 	   	 q.push({xx,yy,s1.step+1});
			   }
		    }
		 }
		 if(a[s1.x][s1.y]=='B')
		 {
		    for(int i=0;i<4;i++)
		    {
		 	   int xx=s1.x+dx[i]+dx[i],yy=s1.y+dy[i]+dy[i];
		 	   if(xx>0&&yy>0&&xx<=n&&yy<=n&&v[xx][yy]==0&&a[xx][yy]!='*')
		 	   {
		 	   	 v[xx][yy]=1;
		 	   	 q.push({xx,yy,s1.step+1});
			   }
		    }
		 }
		 if(a[s1.x][s1.y]=='C')
		 {
		    for(int i=0;i<4;i++)
		    {
		 	   int xx=s1.x+xd[i],yy=s1.y+yd[i];
		 	   if(xx>0&&yy>0&&xx<=n&&yy<=n&&v[xx][yy]==0&&a[xx][yy]!='*')
		 	   {
		 	   	 v[xx][yy]=1;
		 	   	 q.push({xx,yy,s1.step+2});
			   }
		    }
		 }
	}
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)cin>>a[i][j];
	bfs(1,1);
	bfs(1,n);
	bfs(n,1);
	if(s==1e6)cout<<"No answer";
	else cout<<s;
	return 0;
}