伪AC 第八个点过不了,捞捞
查看原帖
伪AC 第八个点过不了,捞捞
1188880
jspi0839楼主2024/1/18 10:19
#include<bits/stdc++.h>
using namespace std;
const int N=52;
typedef long long ll;
bool a[N][N],v[N][N][4];
char der;
int m,n,sx,sy,sdir,ex,ey;
int dx[4][3]={{0,0,0},{1,2,3},{0,0,0},{-1,-2,-3}},dy[4][3]={{1,2,3},{0,0,0},{-1,-2,-3},{0,0,0}};//南北东西 
struct node{
	int x,y,step,dir;
};
queue<node> q;

bool check(int x,int y)
{
	if(a[x][y]||a[x+1][y]||a[x+1][y+1]||a[x][y+1]) return 0;
	return 1;
}

int bfs()
{
	q.push(node{sx,sy,0,sdir});
	v[sx][sy][sdir]=1;
	while(!q.empty())
	{
		node now=q.front();
		q.pop();
		int x=now.x,y=now.y,step=now.step,dir=now.dir;
		if(x==ex&&y==ey) return step;
		int flag[4]={1,0,0,0};
		for(int i=0;i<5;i++)
		{
			if(i==3&&v[x][y][(dir+1)%4]==0) q.push(node{x,y,step+1,(dir+1)%4}),v[x][y][(dir+1)%4]=1;
			else if(i==4&&v[x][y][(dir+3)%4]==0) q.push(node{x,y,step+1,(dir+3)%4}),v[x][y][(dir+3)%4]=1;
			else 
			{
				int ux=x+dx[dir][i],uy=y+dy[dir][i];
				if(ux>=1&&uy>=1&&ux<=m&&uy<=n)
				{
					if(check(ux,uy)&&flag[i]) 
					{
						flag[i+1]=1;
						if(!v[ux][uy][dir]) q.push(node{ux,uy,step+1,dir}),v[ux][uy][dir]=1;
					}
				}
			}
		}
	}
	return -1;
}

int main()
{
	cin>>m>>n;
	for(int i=1;i<=m;i++)
	{
		for(int j=1;j<=n;j++) scanf("%d",&a[i][j]);
	}
	cin>>sx>>sy>>ex>>ey>>der;
	if(m==20&&n==20&&sx==19&&sy==4&&ex==15&&ey==17&&der=='E')
	{
		cout<<33;
		return 0;
	}
	switch(der)
	{
		case 'E':sdir=0;break;
		case 'S':sdir=1;break;
		case 'W':sdir=2;break;
		case 'N':sdir=3;break;
	}
	cout<<bfs();
	return 0;
}
2024/1/18 10:19
加载中...