棋盤上的距離，棋盤距離

棋盤上的距離，棋盤距離

問題描述
國際象棋的棋盤是黑白相間的 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;
        }

    }

}