PTA航船

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;
}
上一篇:co-culture-20210304


下一篇:文献学习(part31)--Discovery of time-inconsecutive co-movement patterns of foreign currencies using ...