警示后人

AC代码 掉头并前进

#include<iostream>
#include<queue>
using namespace std;
struct Node
{
	int dis,x,y,dir;
	bool operator < (const Node &x) const
	{
		return x.dis<dis;
	}
};
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
int n,m,direction,target_X,target_Y,start_X,start_Y;
bool vis[50][50][4],a[50][50];

bool check(Node tmp)
{
	return a[tmp.x+dx[tmp.dir]][tmp.y+dy[tmp.dir]]||a[tmp.x+dx[(tmp.dir+1)%4]][tmp.y+dy[(tmp.dir+1)%4]]||a[tmp.x+dx[(tmp.dir+3)%4]][tmp.y+dy[(tmp.dir+3)%4]];
}
void bfs()
{
	priority_queue <Node> q;
	Node now,tmp;
	tmp.dir=direction;
	tmp.x=start_X;
	tmp.y=start_Y;
	tmp.dis=0;
	q.push(tmp);
	while(!q.empty())
	{
		now=q.top();
		q.pop();
		if(now.x==target_X&&now.y==target_Y)
		{
			cout<<now.dis<<endl;
			return ;
		}
		if(vis[now.x][now.y][now.dir])
			continue;
		vis[now.x][now.y][now.dir]=1;
		tmp=now;
		tmp.x=now.x+dx[now.dir];
		tmp.y=now.y+dy[now.dir];
		if(a[tmp.x][tmp.y]&&!vis[tmp.x][tmp.y][tmp.dir])
			q.push(tmp);
		tmp.x=now.x+dx[(now.dir+3)%4];
		tmp.y=now.y+dy[(now.dir+3)%4];
		tmp.dir=(now.dir+3)%4;
		tmp.dis=now.dis+1;
		if(a[tmp.x][tmp.y]&&!vis[tmp.x][tmp.y][tmp.dir])
			q.push(tmp);
		tmp.x=now.x+dx[(now.dir+1)%4];
		tmp.y=now.y+dy[(now.dir+1)%4];
		tmp.dir=(now.dir+1)%4;
		tmp.dis=now.dis+5;
		if(a[tmp.x][tmp.y]&&!vis[tmp.x][tmp.y][tmp.dir])
			q.push(tmp);
		tmp.x=now.x+dx[(now.dir+2)%4];
		tmp.y=now.y+dy[(now.dir+2)%4];
		tmp.dis=now.dis+10;
		tmp.dir=(now.dir+2)%4;
		if(a[tmp.x][tmp.y]&&!vis[tmp.x][tmp.y][tmp.dir]&&!check(now))
			q.push(tmp);
	}
}

int main()
{
	cin>>n>>m;
	char c;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			cin>>c;
			switch(c)
			{
				case '.':
					a[i][j]=0;
					break;
				case '#':
					a[i][j]=1;
					break;
				case 'F':
					a[i][j]=1;
					target_X=i;
					target_Y=j;
					break;
				case 'E':
					a[i][j]=1;
					start_X=i;
					start_Y=j;
					direction=0;
					break;
				case 'S':
					a[i][j]=1;
					start_X=i;
					start_Y=j;
					direction=1;
					break;
				case 'W':
					a[i][j]=1;
					start_X=i;
					start_Y=j;
					direction=2;
					break;
				case 'N':
					a[i][j]=1;
					start_X=i;
					start_Y=j;
					direction=3;
					break;
			}
		}
	bfs();
	system("pause");
	return 0;
}

80代码 原地调头 WA#4

#include<iostream>
#include<queue>
using namespace std;
struct Node
{
	int dis,x,y,dir;
	bool operator < (const Node &x) const
	{
		return x.dis<dis;
	}
};
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
int n,m,direction,target_X,target_Y,start_X,start_Y;
bool vis[50][50][4],a[50][50];

bool check(Node tmp)
{
	return a[tmp.x+dx[tmp.dir]][tmp.y+dy[tmp.dir]]||a[tmp.x+dx[(tmp.dir+1)%4]][tmp.y+dy[(tmp.dir+1)%4]]||a[tmp.x+dx[(tmp.dir+3)%4]][tmp.y+dy[(tmp.dir+3)%4]];
}
void bfs()
{
	priority_queue <Node> q;
	Node now,tmp;
	tmp.dir=direction;
	tmp.x=start_X;
	tmp.y=start_Y;
	tmp.dis=0;
	q.push(tmp);
	while(!q.empty())
	{
		now=q.top();
		q.pop();
		if(now.x==target_X&&now.y==target_Y)
		{
			cout<<now.dis<<endl;
			return ;
		}
		if(vis[now.x][now.y][now.dir])
			continue;
		vis[now.x][now.y][now.dir]=1;
		tmp=now;
		tmp.x=now.x+dx[now.dir];
		tmp.y=now.y+dy[now.dir];
		if(a[tmp.x][tmp.y]&&!vis[tmp.x][tmp.y][tmp.dir])
			q.push(tmp);
		tmp.x=now.x+dx[(now.dir+3)%4];
		tmp.y=now.y+dy[(now.dir+3)%4];
		tmp.dir=(now.dir+3)%4;
		tmp.dis=now.dis+1;
		if(a[tmp.x][tmp.y]&&!vis[tmp.x][tmp.y][tmp.dir])
			q.push(tmp);
		tmp.x=now.x+dx[(now.dir+1)%4];
		tmp.y=now.y+dy[(now.dir+1)%4];
		tmp.dir=(now.dir+1)%4;
		tmp.dis=now.dis+5;
		if(a[tmp.x][tmp.y]&&!vis[tmp.x][tmp.y][tmp.dir])
			q.push(tmp);
		tmp.dis=now.dis+10;
		tmp.dir=(now.dir+2)%4;
		if(!check(now)&&!vis[tmp.x][tmp.y][tmp.dir])
			q.push(tmp);
	}
}

int main()
{
	cin>>n>>m;
	char c;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			cin>>c;
			switch(c)
			{
				case '.':
					a[i][j]=0;
					break;
				case '#':
					a[i][j]=1;
					break;
				case 'F':
					a[i][j]=1;
					target_X=i;
					target_Y=j;
					break;
				case 'E':
					a[i][j]=1;
					start_X=i;
					start_Y=j;
					direction=0;
					break;
				case 'S':
					a[i][j]=1;
					start_X=i;
					start_Y=j;
					direction=1;
					break;
				case 'W':
					a[i][j]=1;
					start_X=i;
					start_Y=j;
					direction=2;
					break;
				case 'N':
					a[i][j]=1;
					start_X=i;
					start_Y=j;
					direction=3;
					break;
			}
		}
	bfs();
	system("pause");
	return 0;
}

区别在

tmp.x=now.x+dx[(now.dir+2)%4];
		tmp.y=now.y+dy[(now.dir+2)%4];
		tmp.dis=now.dis+10;
		tmp.dir=(now.dir+2)%4;
		if(a[tmp.x][tmp.y]&&!vis[tmp.x][tmp.y][tmp.dir]&&!check(now))
			q.push(tmp);

和

		tmp.dis=now.dis+10;
		tmp.dir=(now.dir+2)%4;
		if(!check(now)&&!vis[tmp.x][tmp.y][tmp.dir])
			q.push(tmp);