ZeroJudge C117: Knight Moves

UVa 00439 – Knight Moves

Your friend is researching the Traveling Knight Problem in chess, and he wants you to help him solve a problem: Given the positions X and Y of two squares, find out the minimum number of steps required for the knight to move from X to Y.

Sample Inputs/Outputs

Sample Input(s)Sample Output(s)
EOF input. Each test case consists of one line. Each line contains the positions of two chess squares. Each position is represented by a letter (a–h, representing the column on the chessboard) and a number (1–8, representing the row on the chessboard).For each input line, output '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 Sample Test Cases

Thought Process

When collecting the data, use two strings to store the starting point and the destination. You can use a Pair to store them, where Pair.first represents the numerical part and Pair.second represents the alphabetical part. You can use 'alphabet - 'a' + 1' to convert the letter to a number. Remember to add 1 because BFS runs on a 1-based index.

The concept is similar to a regular BFS, but instead of moving up, down, left, or right, you need to move according to the knight's moves in chess. You can declare an array int loc[8][2] = {{-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}}; these represent the knight's moves. Remember not to move to the same point twice, you can use a Map to keep track of visited points.

You can initialize a count variable to 0, and increment it each time you call BFS. When you find the destination, return count.

Sample Code－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
Tags

Related Posts

Comments