問題描述

國際象棋的棋盤是黑白相間的 8 * 8 的方格，棋子放在格子中間。如下圖所示：

王、后、車、象的走子規(guī)則如下：

寫一個程序，給定起始位置和目標(biāo)位置，計算王、后、車、象從起始位置走到目標(biāo)位置所需的最少步數(shù)。

輸入數(shù)據(jù)

        第一行是測試數(shù)據(jù)的組數(shù) t（ 0 <= t <= 20）。以下每行是一組測試數(shù)據(jù)，每組包括棋盤上的兩個位置，第一個是起始位置，第二個是目標(biāo)位置。位置用"字母-數(shù)字"的形式表示，字母從"a"到"h"，數(shù)字從"1"到"8"。

輸出要求

      對輸入的每組測試數(shù)據(jù)，輸出王、后、車、象所需的最少步數(shù)。如果無法到達,就輸出"Inf".

輸入樣例

2a1 c3f5 f8
輸出樣例
2 1 2 13 1 1 Inf
解題思路
        這個問題是給定一個棋盤上的起始位置和終止位置，分別判斷王、后、車、象從起始位置到達終止位置需要的步數(shù)。首先，王、后、車、象彼此獨立，分別考慮就可以了。所以這個題目重點要分析王、后、車、象的行走規(guī)則特點，從而推出它們從起點到終點的步數(shù)。我們假設(shè)起始位置與終止位置在水平方向上的距離是 x，它們在豎直方向上的距離是 y。       根據(jù)王的行走規(guī)則，他可以橫、直、斜走， 每步限走一格，所以需要的步數(shù)是 min(x,y)+abs(x-y)– 即 x， y 中較小的一個加上 x 與 y 之差的絕對值。       根據(jù)后行走的規(guī)則，她可以橫、直、斜走，每步格數(shù)不受限制，所以需要的步數(shù)是 1（ x 等于 y 或者 x 等于 0 或者 y 等于 0）或者2(x 不等于 y)。       根據(jù)車行走的規(guī)則，它可以橫、豎走，不能斜走，格數(shù)不限，需要步數(shù)為 1（ x 或者 y 等于 0）或者 2(x 和 y 都不等于 0)。       根據(jù)象行走得規(guī)則，它可以斜走，格數(shù)不限。棋盤上的格點可以分為兩類，第一類是它的橫坐標(biāo)和縱坐標(biāo)之差為奇數(shù)，第二類是橫縱坐標(biāo)之差為偶數(shù)。對于只能斜走的象，它每走一步，因為橫縱坐標(biāo)增加或減小的絕對值相等，所以橫坐標(biāo)和縱坐標(biāo)之差的奇偶性無論如何行走都保持不變。因此，上述的第一類點和第二類點不能互相到達。如果判斷出起始點和終止點分別屬于兩類點，就可以得出它們之間需要無數(shù)步的結(jié)論。如果它們屬于同一類點，象從起始點走到終止點需要 1（ x 的絕對值等于 y 的絕對值）或者 2（ x 的絕對值不等于 y 的絕對值）。
參考程序
#include <iostream>#include <cmath>using namespace std;int main(){	int nCases,i;	cin >> nCases;	for(i=0;i<nCases;i++){		char begin[5],end[5];		cin>>begin>>end;		int x,y;		//用 x 和 y 分別存儲起止位置之間 x 方向和 y 方向上的距離。		x = abs(begin[0]-end[0]);		y = abs(begin[1]-end[1]);		if(!x&&!y){			//起止位置相同，所有棋子都走 0 步。			cout<<"0 0 0 0"<<endl;		}else{			// 王的步數(shù)			if(x<y){				cout<<y;			}else{				cout<<x;			}			// 后的步數(shù)			if(x==y || !x || !y){				cout<<" 1";			}else{				cout<<" 2";			}			// 車的步數(shù)			if(!x || !y){				cout<<" 1";			}else{				cout<<" 2";			}			// 象的步數(shù)			if(abs(x-y)%2 != 0){				cout<<" Inf"<<endl;			}else if(x == y){				cout<<" 1"<<endl;			}else{				cout<<" 2"<<endl;			}		}	} 	return 0;}