萌新80分求助
查看原帖
萌新80分求助
463202
thatsgame楼主2021/9/12 16:51
#include<cmath>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn=60;
int n,m;
int t;
bool map[maxn][maxn];
bool vis[maxn][maxn][4];
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
bool check(int x,int y)
{
	if(x>0&&x<=n&&y>0&&y<=m)
	return true;
	else return false;
}
struct gps
{
	int x;
	int y;
	int times;
	int dir;
}p;
int sx,sy,ex,ey;
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			scanf("%d",&t);
			if(t)
			{
				map[i][j]=1;
				map[i-1][j]=1;
				map[i-1][j-1]=1;
				map[i][j-1]=1;
			}
		}
	}
	queue <gps> lq;
	char dir1;
	scanf("%d%d%d%d%c",&sx,&sy,&ex,&ey,&dir1);
	gps t1;
	t1.x=sx;
	t1.y=sy;
	t1.times=0;
	if(dir1=='N') t1.dir=0;
	if(dir1=='E') t1.dir=1;
	if(dir1=='S') t1.dir=2;
	if(dir1=='W') t1.dir=3;
	lq.push(t1);
	while(!lq.empty())
	{
		t1=lq.front();
		vis[t1.x][t1.y][t1.dir]=1;
		if(t1.x==ex&&t1.y==ey)
		{
			printf("%d",t1.times);
			return 0;
		}
		gps t=t1;
		t.times++;
		t.dir=(t.dir+1)%4;
		if(!vis[t.x][t.y][t.dir])
		lq.push(t);
		t.dir=(t.dir+2)%4;
		if(!vis[t.x][t.y][t.dir])
		lq.push(t);
		t.dir=t1.dir;
		t.x+=dx[t.dir];
		t.y+=dy[t.dir];
		if(check(t.x,t.y)&&!vis[t.x][t.y][t.dir]&&!map[t.x][t.y])
		{
			lq.push(t);	
			t.x+=dx[t.dir];
			t.y+=dy[t.dir];
			if(check(t.x,t.y)&&!vis[t.x][t.y][t.dir]&&!map[t.x][t.y])
			{
				lq.push(t);	
				t.x+=dx[t.dir];
				t.y+=dy[t.dir];
				if(check(t.x,t.y)&&!vis[t.x][t.y][t.dir]&&!map[t.x][t.y])
				{
					lq.push(t);
				}
			}
		}
		lq.pop();
	}
	printf("-1");
	return 0;
}
2021/9/12 16:51
加载中...