P2060 马步距离(洛谷)

我们无论遇到什么困难,都不要拖,微笑着面对他,战胜拖延的最好方法就是面对拖延。

今天又拖延了……

早晨听完老师讲课,本想做一道题练练手的,结果因为懒,瘫了一上午。最后在固定的刷题时间去面对了这道题,然后就A了

额,这个题的思路是很好想的,虽然数据大了这么亿点点,但不难看出是个广搜吧(根本不是)。

广搜根本不可能啊,数据太大了。但是我们可以发现什么东西,这个棋盘上没有障碍!

谁不知道平时广搜是因为不知道往哪里走才都试一遍的。但这个知道往哪走啊!

都知道怎么走了还广搜个毛线,冲过去就好了,但在最后几步,还是要绕一下的,因为范围实在太小,直接打表不香吗……

所以这个题的标准(简单快捷)的解法就是:贪心+打表。(话说这个题为什么标签有搜索……,可能就是为了骗人。也可能真的有大佬能做出来,但我不会)

总之这个题是真的不错,我觉得可以锻炼我们的思维(因为我懒所以写的更短了)

上代码吧:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
long long cjx,cjy,shu;
long long sz[6][6]=
{
{0,3,2,3,2},
{3,2,1,2,3},
{2,1,4,3,2},
{3,2,3,2,3},
{2,3,2,3,4},
};//这样看着顺眼。也有利于后期查错。而且4个方向的数都一样,就是把坐标翻转一下的事。
long long px,py,sx,sy;//4个变量,多个xy我就会乱起名,还是用题目名称靠谱一些。
int main()
{
	cin>>px>>py>>sx>>sy;
	cjx=abs(sx-px);//算他们之间的距离。
	cjy=abs(sy-py);
	while(true)
	{
		if(cjx<=4&&cjy<=4)//可以打表了。
		{
			cout<<shu+sz[cjx][cjy]<<endl;//中间可能把x和y交换了,但这一点关系都没有,仔细想想就知道了(如果把走过来的路程中所有走法全部反转,x和y就会交换,但移动次数不变)
			return 0;
		}
		if(cjx<cjy)//马那个奇怪的走法,一边走2格一边走1格,向哪边走2格呢?当然是距离目标地点远的那一边。
		{
			swap(cjx,cjy);
		}
		cjx-=2;
		cjy-=1;
		if(cjx<0)//都说了,反转一下的事,再判断在哪个方向多麻烦。
		{
			cjx=0-cjx;
		}else if(cjy<0)
		{
			cjy=0-cjy;
		}
		shu++; 
	}
	return 0;
}

这个代码真的短,道理也很简单,我觉得最难的地方就是看见题目能放弃广搜(看看数据就放弃了),去往这个方面想。只要知道思路,写代码还是很简单的。

原文地址:https://www.cnblogs.com/lichangjian/p/12902036.html