求助!!! 样例输出为6! 只过了2个点
查看原帖
求助!!! 样例输出为6! 只过了2个点
360964
xyt07code楼主2020/7/28 12:54

求助!!! 样例输出为6! 只过了2个点 代码如下

#include<bits/stdc++.h>
using namespace std;
int g[100][100];
int used[100][100][5];
struct point
{
	int x,y,step;
	char di;//di表示现在所面向的方向   
};
point jqr(int i,point n)
{
	if(i == 0)
	{
		if(n.di == 'E') n.x++;
		else if(n.di == 'W') n.x--;
		else if(n.di == 'N') n.y--;
		else if(n.di == 'S') n.y++;
	}
	else if(i == 1)
	{
		if(n.di == 'E') n.x += 2;
		else if(n.di == 'W') n.x -= 2;
		else if(n.di == 'N') n.y -= 2;
		else if(n.di == 'S') n.y += 2;
	}
	else if(i == 2)
	{
		if(n.di == 'E') n.x += 3;
		else if(n.di == 'W') n.x -= 3;
		else if(n.di == 'N') n.y -= 3;
		else if(n.di == 'S') n.y += 3;
	}
	else if(i == 3)//向左转  
	{
		if(n.di == 'E') n.di = 'N';
		else if(n.di == 'W') n.di = 'S';
		else if(n.di == 'N') n.di = 'W';
		else if(n.di == 'S') n.di = 'E';
	}
	else if(i == 4)//向右转   
	{
		if(n.di == 'E') n.di = 'S';
		else if(n.di == 'W') n.di = 'N';
		else if(n.di == 'N') n.di = 'E';
		else if(n.di == 'S') n.di = 'W';
	}
	n.step++;
	return n;
}
point q[10000000];
int main()
{
	int n,m,sn,sm,dn,dm,f=1,t=1,ans=-1;
	char fc;
	memset(used,-1,sizeof(used));
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			scanf("%d",&g[i][j]);
	scanf("%d %d %d %d %c",&sn,&sm,&dn,&dm,&fc);
	q[f].di = fc,q[f].step = 0,q[f].x = sn,q[f].y = sm;
	if(sn == dn && sm == dm)
	{
		printf("0");
		return 0;
	}
	while(f <= t)
	{
		point u = q[f++],v;
		for(int i=0;i<5;i++)
		{
			v = jqr(i,u);
			if(v.x >= n || v.y >= m || v.x < 1 || v.y < 1 || g[v.x][v.y] == 1) continue;
			if(v.x == dn && v.y == dm)
				if(ans < 0 || ans > v.step)
					ans = v.step;
			if(used[v.x][v.y][v.di] == -1 || used[v.x][v.y][v.di] > v.step)
			{
				q[++t] = v;
				used[v.x][v.y][v.di] = v.step;
			}
		}
	}
	printf("%d",ans);
	return 0;
}
2020/7/28 12:54
加载中...