PTA航船

题目描述

航船游戏中，风向每个单位时间会改变一次，每次航船可以选择顺风前行一个单位距离，也可以选择原地不动。游戏时长为 t，请你计算从起点出发，最终到达终点所需要的最少移动次数。如果游戏结束也到达不了终点，则输出-1。

输入格式

第一行包括一个正整数 t（1<=t<=100000）。

第二行为起点坐标（x1 , y1）。

第三行为终点坐标（x2 , y2）。

接下来 t 行，每行输入一个单词，表示风向 。

输出格式

输出为一个整数，为到达终点所需移动的最少步数；如果无法到达，输出-1。

输入样例

在这里给出一组输入。例如：

5 
1 1 
2 2 
east 
north 
west 
west 
north 

输出样例

在这里给出相应的输出。例如：

2

思路

• 第一层：用宽度优先搜索加队列，超时+答案错误
• 第二层：可由曼哈顿距离联想出一个特判，当最大可能步数小于两点的距离差时，绝不可能到达终点。就比如硬要让一个轻骑兵跑完整个戈壁滩一样。（骗了10分）
• 第三层：由于题目问的是最少走几步到达，而不是第几步到达，由贪心的思想可得，可大胆的不去计算与目的地方向相反的步数（不要去走冤枉路，浪费精力）
• 第四层：只要某一个或两个方向的步数超过所需的纵向或横向的阈值，即可证明有到达终点的可能性（且答案是固定的，至少这两个字简直就是出题人的恶意所在）。

代码

#include<iostream>
#include<stdio.h>
#include<cstring>
#include<algorithm>
using namespace std;
int ax,ay,bx,by;
int n,cnt_n,cnt_w,cnt_e,cnt_s;
int find_ans()
{
	int sum=0;
	if(ax<bx)
	{
		if(bx-ax>cnt_e)
		{
			return -1;
		}
		else
		  sum+=bx-ax;
	}
	else if(ax>bx)
	{
		if(ax-bx>cnt_w)
		{
			return -1;
		}
		else
		  sum+=ax-bx;
	}
	
	if(ay<by)
	{
		if(by-ay>cnt_n)
		{
			return -1;
		}
		else
		  sum+=by-ay;
	}
	else if(ay>by)
	{
		if(ay-by>cnt_s)
		{
			return -1;
		}
		else
		  sum+=ay-by;
	}
	return sum;
}
int main()
{	
	int i;
	string s;
	cin>>n;
    cin>>ax>>ay>>bx>>by;
    for(i=0;i<n;i++)
    {
    	cin>>s;
    	switch (s[0])
		{
    		case 'n':cnt_n++;break;
    		case 'w':cnt_w++;break;
    		case 'e':cnt_e++;break;
    		case 's':cnt_s++;break;
		}
	}
	
	cout<<find_ans();
	return 0;
}

• 伤心地（错误代码）

#include<iostream>
#include<stdio.h>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
int ax,ay,bx,by;
int dir[100005];
int pos=0;
int flag=0;
int dx[4]={0,0,-1,1};
int dy[4]={1,-1,0,0};
typedef struct{
	int cx;
	int cy;
	int co;
}node;

int bfs()
{
	
    queue<node > q;
    node node_1;
    node_1.cx=ax;
    node_1.cy=ay;
    node_1.co=0;
    q.push(node_1);
    while(!q.empty())
    {
    	node cur_node=q.front();
    	
    	q.pop();
    	if(cur_node.cx+dx[dir[cur_node.co]]==bx&&cur_node.cy+dy[dir[cur_node.co]]==by)
    	   return cur_node.co+1;
    	node new_node;
		new_node.cx =cur_node.cx+dx[dir[cur_node.co]];
		new_node.cy =cur_node.cy+dy[dir[cur_node.co]];  
		new_node.co =cur_node.co+1;
    	q.push(new_node);
    	new_node.cx =cur_node.cx;
		new_node.cy =cur_node.cy;  
		new_node.co =cur_node.co+1;
    	q.push(new_node);
	}
	return -1;
}
int main()
{
	int n;
	int i;
	string s;
	cin>>n;
	cin>>ax>>ay>>bx>>by;
	if(n<(bx-ax)+(by-ay))
	{
		cout<<-1;
		return 0;
	}
	for(i=0;i<n;i++)
	{
		cin>>s;
		switch (s[0]){
			case 'n':dir[pos++]=0;break;
			case 's':dir[pos++]=1;break;
			case 'w':dir[pos++]=2;break;
			case 'e':dir[pos++]=3;break;
		}
			
	}
	int answer=bfs();
	cout<<answer;
	return 0;
}