求救，真的迷惑了（注释+详细调试结果）
查看原帖
求救，真的迷惑了（注释+详细调试结果）
242524
JRzyh楼主2021/8/20 14:52

目前的问题是搜到一般就莫名搜不下去了

样例过不了

很显然，这道题因为机器人走在格线上，把障碍物转化成在格线上更好算

转化后地图：

0 0 0 0 0 0 1 1 0 0 0
0 0 0 0 0 0 1 1 1 1 0
0 0 0 1 1 0 0 0 1 1 0
0 0 1 1 1 0 0 0 0 0 0
0 0 1 1 0 0 1 1 0 0 0
0 0 0 0 0 1 1 1 0 0 0
0 0 0 1 1 1 1 0 0 0 0
0 0 0 1 1 1 0 0 0 0 0
1 1 0 0 0 0 0 0 1 1 0
1 1 0 0 0 0 0 0 1 1 0

这是我的代码 bfs 到的位置，四个数分别是x,y,朝向,时间;

7 2 1 0
7 2 3 1
7 2 2 1
7 1 1 1
7 2 0 2
6 2 3 2
5 2 3 2
4 2 3 2
8 2 2 2
7 1 3 2
7 1 2 2
7 2 2 3
7 3 0 3
6 2 0 3
6 2 1 3
3 2 3 3
5 2 0 3
5 2 1 3
2 2 3 3
4 2 0 3
4 2 1 3
1 2 3 3
8 2 1 3
8 2 0 3
7 1 0 3
6 1 3 3
5 1 3 3
4 1 3 3
8 1 2 3
7 3 2 4
7 3 3 4
6 2 2 4
6 3 0 4
6 4 0 4
6 1 1 4
3 2 0 4
3 2 1 4
5 2 2 4
5 1 1 4
2 2 0 4
2 2 1 4
4 2 2 4
4 1 1 4
1 2 0 4
1 2 1 4
8 2 3 4
8 1 1 4
8 3 0 4
7 1 2 4
6 1 0 4
3 1 3 4
5 1 0 4
2 1 3 4
4 1 0 4
1 1 3 4
8 1 0 4
7 3 1 5
8 3 2 5
6 3 3 5
6 2 1 5
6 3 2 5
6 4 2 5
6 4 3 5
6 1 2 5
3 2 2 5
3 3 0 5
3 1 1 5
5 2 1 5
5 1 2 5
2 2 2 5
2 3 0 5
2 4 0 5
2 5 0 5
2 1 1 5
4 2 1 5
4 1 2 5
1 2 2 5
1 3 0 5
1 4 0 5
1 5 0 5
1 1 1 5
8 2 0 5
8 1 3 5
8 3 3 5
6 1 2 5
5 1 2 5
4 1 2 5
1 1 0 5
7 3 3 6
8 3 1 6
6 3 1 6
6 3 1 6
6 4 1 6
3 2 1 6
3 3 2 6
3 3 3 6
3 1 2 6
2 2 1 6
2 3 2 6
2 3 3 6
2 4 2 6
2 4 3 6
2 5 2 6
2 1 2 6
1 2 1 6
1 3 2 6
1 3 3 6
1 4 2 6
1 4 3 6
1 5 2 6
1 1 2 6
8 1 0 6
1 1 2 6
8 3 3 7
6 4 3 7
3 3 1 7
2 3 3 7
1 3 3 7
2 3 1 7
2 4 1 7
1 4 3 7
1 3 1 7
1 4 1 7
3 3 3 8
2 4 3 8

其中朝向的表示为

0:^
1:v
2:>
3:<

把上面的位置表在图上：

2表示走到的，1表示障碍，s是起点

2 2 2 2 2 0 1 1 0 0 0
2 2 2 2 2 0 1 1 1 1 0
2 2 2 1 1 0 0 0 1 1 0
2 2 1 1 1 0 0 0 0 0 0
2 2 1 1 0 0 1 1 0 0 0
2 2 2 2 0 1 1 1 0 0 0
2 2 2 1 1 1 1 0 0 0 0
2 2 S 1 1 1 0 0 0 0 0
1 1 0 0 0 0 0 0 1 1 0
1 1 0 0 0 0 0 0 1 1 0

注意到有一半地图没有走到，猜想是转向出了问题。

求帮助

////////////////////////
///////////////////////
//////////////////////
/////////////////////
/////Author/////////
//////zyh//////////
//////////////////
/////////////////
////////////////
///////////////
//////////////
/////////////
////////////
#include<bits/stdc++.h>
#define EL putchar('\n')
#define SP putchar(' ')
using namespace std;
int read(){int x;scanf("%d",&x);return x;}
long long readll(){long long x;scanf("%lld",&x);return x;}
void print(int x){printf("%d",x);}
void print(long long x){printf("%lld",x);}
struct node
{
	int x,y,dis,to;
	node(int _x,int _y,int _to,int _dis=0){x=_x;y=_y;dis=_dis;to=_to;}
	/*
	to:
		0:^
		1:v
		2:>
		3:< 
	*/
};
int cton(char c)//方向字母变数字 
{
	if(c=='N')return 0;
	if(c=='S')return 1;
	if(c=='E')return 2;
	if(c=='W')return 3;
}
int turnright(int x)//右转 
{
	if(x==0)return 2;
	if(x==1)return 3;
	if(x==2)return 1;
	if(x==3)return 0;
} 
int turnleft(int x)//左转 
{
	if(x==0)return 3;
	if(x==1)return 2;
	if(x==2)return 0;
	if(x==3)return 1;
} 
node Creep(node x)//走一步 
{
	if(x.to==0)x.y+=1;
	if(x.to==1)x.y-=1;
	if(x.to==2)x.x+=1;
	if(x.to==3)x.x-=1;
	return x;
} 
queue<node>q;
bitset<60>b[60][4]/*判走过*/,c[60]/*判障碍*/;
int n,m,x,y,tx,ty;
char ch;
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			int a=read();
			if(a==1)
			{
				c[i][j]=c[i][j+1]=c[i+1][j+1]=c[i+1][j]=1;//考虑交点不考虑格子 
			}
		}
	}
	/*
	for(int i=1;i<=n+1;i++)
	{
		for(int j=1;j<=m+1;j++)
		{
			cout<<c[i][j]<<" ";
		}
		EL;
	}
	*/
	cin>>x>>y>>tx>>ty>>ch;
	q.push(node(x,y,cton(ch)));//start 
	b[x][y][cton(ch)]=1;
	while(!q.empty())
	{
		node t=q.front();
		q.pop();
		//cout<<t.x<<" "<<t.y<<" "<<t.to<<" "<<t.dis<<endl; //调试 
		if(t.x==tx&&t.y==ty)//搜到输出 
		{
			cout<<t.dis;
			return 0;
		}
		if(!b[t.x][t.y][turnright(t.to)])//右转没走过 
		{
			q.push(node(t.x,t.y,turnright(t.to),t.dis+1));//右转
			b[t.x][t.y][turnright(t.to)]=1;
		}
		if(!b[t.x][t.y][turnleft(t.to)])//左转没走过
		{
			q.push(node(t.x,t.y,turnleft(t.to),t.dis+1));//左转
			b[t.x][t.y][turnright(t.to)]=1;
		}
		node temp=t;
		for(int i=1;i<=3;i++)//可以 走三步 
		{
			temp=Creep(temp);//前进一步 
			if(temp.x<1||temp.x>=n||temp.y<1||temp.y>=m||c[temp.x][temp.y])break;//遇到障碍停 
			if(!b[temp.x][temp.y][temp.to])//假如没走过 
			{
				q.push(node(temp.x,temp.y,temp.to,t.dis+1));//那我走 
				b[temp.x][temp.y][temp.to]=1;
			}
		}
	}
 	return 0;
}
2021/8/20 14:52