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. |
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