首页 > 代码库 > 棋盘上的距离
棋盘上的距离
问题描述
国际象棋的棋盘是黑白相间的 8 * 8 的方格,棋子放在格子中间。如图所示:
王、后、车、象的走子规则如下:
? 王:横、直、斜都可以走,但每步限走一格。
? 后:横、直、斜都可以走,每步格数不受限制。
? 车:横、竖均可以走,不能斜走,格数不限。
? 象:只能斜走,格数不限。
写一个程序,给定起始位置和目标位置,计算王、后、车、象从起始位置走到目标位置所需的最少步数。
输入数据
第一行是测试数据的组数 t(0 <= t <= 20)。以下每行是一组测试数据,每组包括棋盘 上的两个位置,第一个是起始位置,第二个是目标位置。位置用"字母-数字"的形式表示, 字母从"a"到"h",数字从"1"到"8"。
输出要求
对输入的每组测试数据,输出王、后、车、象所需的最少步数。如果无法到达,就输出 "Inf".
输入样例
2
a1 c3
f5 f8
输出样例
2 1 2 1
3 1 1 Inf
解题思路：
1 先考虑特例:
(1)何时会出新inf。易知王车后可以到达任何一点。但是象不能到达任何一点。
可以这么考虑，初始的象如果是白色，那么不管其如何移动仍然会是白色。反之亦然。
具体的数学表达为x-y的奇偶性
2 设横向距离为x 纵向距离为y 那么
(1)因为王斜走一步等于先横一步再竖一步，所以王斜走的越多越好，王斜走最多为min(x,y)，为达到终点还要走|x-y|
所以王最小的距离为 min(x,y)+|x-y|＝max(x,y)
(2)车只有横移和竖移，所以如果在一条线上，那么为1 否则为2
(3)皇后 当 x＝0 or y＝0 一步到达 当 y=x 一步到达
其他情况 两步
(4) 象 只能斜走 象每走一步，纵横坐标增加减少相同 但是差值的奇偶性不变 所以通过此值判断是否可以到达
如果x=y则一步 否则两步
c++实现：
#include <iostream>using namespace std;int main() { int n; cin>>n; char start[3]; char end[3]; for(int i=0;i<n;i++) { cin>>start>>end; int x=abs(start[0]-end[0]); int y=abs(start[1]-end[1]); //does not need to move if(x==0&&y==0) { cout<<"0 0 0 0"<<endl; continue; } //for king cout<< (x>y?x:y)<<" "; //for queen cout<<(x==0||y==0||x==y?1:2)<<" "; //for car cout<< (x==0||y==0?1:2)<<" "; //for ele if((x-y)%2==0) { if(x==y) { cout<<"1"<<endl; } else { cout<<"2"<<endl; } } else { cout<<"Inf"<<endl; } }}
棋盘上的距离