POJ1657 Bailian1657 Distance on Chessboard【基礎】

Distance on Chessboard

描述

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

王、後、車、象的走子規則如下：

王：橫、直、斜都可以走，但每步限走一格。

後：橫、直、斜都可以走，每步格數不受限制。

車：橫、豎均可以走，不能斜走，格數不限。

象：隻能斜走，格數不限。

寫一個程式，給定起始位置和目标位置，計算王、後、車、象從起始位置走到目标位置所需的最少步數。

輸入

第一行是測試資料的組數t（0 <= t <= 20）。以下每行是一組測試資料，每組包括棋盤上的兩個位置，第一個是起始位置，第二個是目标位置。位置用"字母-數字"的形式表示，字母從"a"到"h"，數字從"1"到"8"。

輸出

對輸入的每組測試資料，輸出王、後、車、象所需的最少步數。如果無法到達,就輸出"Inf".

樣例輸入

2

a1 c3

f5 f8

樣例輸出

2 1 2 1

3 1 1 Inf

來源

POJ Monthly–2004.05.15 Liu [email protected]

問題連結：POJ1657 Bailian1657 Distance on Chessboard

問題描述：（略）

問題分析：

    這個問題是給出棋盤上的起始位置，分别計算王後車象從起始位置到達終止位置所需的步數。可以先算出橫向坐标的內插補點dx和縱向坐标的內插補點dy。起止位置相同時，隻需要走0步。

    分别考慮王後車象的行走規則，王可以直走、橫走和邪走，是以所需要走的步數為dx和dy中較大的；後可以八個方向行走，是以處在同行、同列和同一邪線上則走1步就到目标位置，否則走2步即可；車可以橫走也可以豎走，如果在同一行或同一列上則走1步就到目标位置，否則走2步就可以到目标位置;象是走邪線，有黑象和白象之分，如果在同一邪線上則1步可到目标位置，如果在同一顔色的邪線上最多2步可以到達目标位置，否則就不可到達目标位置。

程式說明：

    數組ans[]的元素分别用于存儲王後車象的步數。計算與輸出邏輯分開。

參考連結：（略）

題記：（略）

AC的C語言程式如下：

/* POJ1657 Bailian1657 Distance on Chessboard */

#include <stdio.h>
#include <stdlib.h>

#define MAX(x, y) (((x) > (y)) ? (x) : (y))

#define N 4

int main(void)
{
    int t, kcnt, qcnt, rcnt, bcnt;

    scanf("%d", &t);
    while(t--) {
        char start[3], end[3];
        scanf("%s%s", start, end);

        int dx = abs(end[0] - start[0]);
        int dy = abs(end[1] - start[1]);
        if(dx == 0 && dy == 0)
            kcnt = qcnt = rcnt = bcnt = 0;  /*王後車象的步數*/
        else {
            kcnt= MAX(dx, dy);
            qcnt = (dx == dy || dx == 0 || dy == 0) ? 1 : 2;
            rcnt = (dx == 0 || dy == 0) ? 1 : 2;
            if(dx == dy)
                bcnt = 1;
            else if(abs(dx - dy) % 2 != 0)
                bcnt = -1;
            else
                bcnt = 2;
        }

        printf("%d %d %d ", kcnt, qcnt, rcnt);
        if(bcnt == -1)
            printf("Inf\n");
        else
            printf("%d\n", bcnt);
    }

    return 0;
}