「HNOI2006」马步距离

发表于 | 分类于 | | 浏览量： 次

这题有点水QwQ…

传送门

洛谷P2060

BZOJ1193

题解

首先很显然不能直接贪心，直接贪心有可能WA，所以要写个DFS之类的东西来搜。

但是数据稍微有点大QwQ，搜不出来。

不难发现，当距离比较远时直接贪心地奔着目标走是肯定没问题的。

所以距离远时贪心，距离近时爆搜就行了QwQ。

其实手玩就能把表打出来。

代码

打表万岁

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<cstdio>
using namespace std;
const int f[7][7]=
{
	{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}
};
int xp,yp,xs,ys,x,y,ans;
int ABS(int x){return x<0?-x:x;}
int main()
{
	scanf("%d%d%d%d",&xp,&yp,&xs,&ys);
	x=ABS(xp-xs);y=ABS(yp-ys);
	while(x>4||y>4)
	{
		if(x<y){x--;y-=2;}
		else{x-=2;y--;}
		if(x<0) x=-x;if(y<0) y=-y;
		ans++;
	}
	ans+=f[x][y];
	printf("%d\n",ans);
	return 0;
}