Description

已知西洋棋規則中

騎士一共有如下圖的八種走法

 

給定兩個 8 x 8 棋盤上的點 (X1, Y1)、(X2, Y2)

請算出騎士從 (X1, Y1) 最少需要走幾步可以到 (X2, Y2)

 

註:
1. (X1, Y1) 一定走得到 (X2, Y2)
2. 從 (X1, Y1) 走到下一個點才算第一步，(X1, Y1) 自己本身不是第一步

 

hint:

#include 

#define INF 2147483647
#define SIZE 8

/*
騎士的八種走法
每一列代表一種走法 x 和 y 的位移量
*/
int Move[8][2] = {
     1, -2,
     2, -1,
     2,  1,
     1,  2,
    -1,  2,
    -2,  1,
    -2, -1,
    -1, -2
};

int X1, Y1;
int X2, Y2;
int min;

int valid(int board[SIZE][SIZE], int x, int y, int path);
void knightMove(int board[SIZE][SIZE], int x, int y, int step);

int main()
{
    /* board 記錄每一格走過了沒 */
    int board[SIZE][SIZE] = {0};

    while (scanf("%d %d %d %d", &X1, &Y1, &X2, &Y2) != EOF) {
        min = INF;

        if (X1==X2 && Y1==Y2) {
            printf("0\n");
        }
        else {
             /* 注意!!! board內的順序為Y、X */
             board[Y1][X1] = 1;
             knightMove(board, X1, Y1, 1);
             board[Y1][X1] = 0;

             printf("%d\n", min);
        }
    }

    return 0;
}

/*
判斷是否超出棋盤、是否已經走過
path 代表是第幾種走法
*/
int valid(int board[SIZE][SIZE], int x, int y, int path)
{
    int next_x, next_y;

    next_x = x + Move[path][0];
    next_y = y + Move[path][1];

    /*
        ???
    */
}

/* 傳入騎士現在的位置以及要尋找的是第幾步 */
void knightMove(int board[SIZE][SIZE], int x, int y, int step)
{
    int next_x, next_y;
    int i;

    if (step >= min) {
        return;
    }
    for (i = 0; i < 8; ++i) {
        if (valid(board, x, y, i) == 1) {
            /*
                ???
            */
        }
    }
}

Input

X1⁽¹⁾  Y1⁽¹⁾  X2⁽¹⁾  Y2⁽¹⁾

X1⁽²⁾  Y1⁽²⁾  X2⁽²⁾  Y2⁽²⁾

...

X1^(N)  Y1^(N)  X2^(N)  Y2^(N)

 

註: 0 <= X1⁽ⁱ⁾, Y1⁽ⁱ⁾, X2⁽ⁱ⁾, Y2⁽ⁱ⁾ < 8 , for i=1, 2, ... , N

N為不超過20的正整數

Output

步數₁

步數₂

...

步數_N

 

註: 最後須加上換行

Sample Input  Download

Sample Output  Download

Tags

Discuss