ZeroJudge C117: Knight Moves

同題：UVa 00439 – Knight Moves

你的一個朋友正在做一個關於西洋棋中騎士旅行問題 (Traveling Knight Problem) 的研究，他希望你幫他解決一個問題：就是給你 2 個格子的位置 X 及 Y，請你找出騎士從 X 走到 Y 最少需要走幾步。

範例測資

範例輸入範例輸出
EOF 輸入，每筆測試資料一列。每列有 2 個西洋棋的座標位置。每個位置座標是由一個英文字母 (a～h，代表棋盤的第幾欄) 及一個數字 (1～8，代表棋盤的第幾列) 組成。對每一列輸入，請輸出「To get from xx to yy takes N knight moves.」。
e2 e4
a1 b2
b2 c3
a1 h8
a1 h7
h8 a1
b1 c3
f6 f6		To get from e2 to e4 takes 2 knight moves.
To get from a1 to b2 takes 4 knight moves.
To get from b2 to c3 takes 2 knight moves.
To get from a1 to h8 takes 6 knight moves.
To get from a1 to h7 takes 5 knight moves.
To get from h8 to a1 takes 6 knight moves.
To get from b1 to c3 takes 1 knight moves.
To get from f6 to f6 takes 0 knight moves.
ZeroJudge C117 範例測資

解題思路

收資料的時候使用兩個字串將起點跟終點收起來，可以使用 Pair<int, int> 來存，Pair.first 就會是數字的部分，Pair.second 會是 字母的部分，可以用「字母 – ‘a’ + 1」將字母換成數字，記得要+1因為BFS跑的是 1-Base。

跟普通的 BFS 概念相同，只是不是上下左右走，要用西洋棋的騎士的走法走 BFS，可以宣告一個陣列 int loc[8][2] = {{-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}}，這些就是騎士的走法，記得不能重複走到相同的點上，可以使用 Map 來紀錄。

可以預設一個 count 變數為 0，每一次重新呼叫 BFS 時就將 count++。當找到終點了就 return count。

範例程式碼－ZeroJudge C117: Knight Moves

#include <iostream>
#include <map>
#include <vector>
using namespace std;

pair<int, int> start, finish;
int loc[8][2] = {{-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}};

pair<int, int> axis (const int a, const int b) {
    pair<int, int>tmp;
    tmp.first = a;
    tmp.second = b;
    return tmp;
}

int BFS(const vector<pair<int, int>>&start, map<pair<int, int>, int>MAP, int count) {
    if (start.size() == 0) return count;
    vector<pair<int, int>>newStart;
    for (auto & i : start) {
        MAP[i]++;
        if (i == finish) return count;
        const int y = i.first, x = i.second;
        for (int j = 0; j<8; j++) {
            const int yy = y+loc[j][0], xx = x+loc[j][1];
            if (yy > 0 && yy <= 8 && xx > 0 && xx <= 8 && MAP[axis(yy, xx)] == 0) {
                newStart.push_back(axis(yy, xx));
            }
        }
    }
    return BFS(newStart, MAP, count+1);
}

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    string a, b;
    while (cin >> a >> b) {
        start = axis(a[1] - '0', a[0] - 'a' + 1);
        finish = axis(b[1] - '0', b[0] - 'a' + 1);
        vector<pair<int, int>>begin;
        begin.push_back(start);
        map<pair<int, int>, int>MAP;
        cout << "To get from " << a << " to " << b << " takes " << BFS(begin, MAP, 0) << " knight moves.\n";
    }
}

//ZeroJudge C117
//Dr. SeanXD
標籤

相關文章

發佈留言