UVa 439 Knight Moves

想法：
　　西洋棋Knight的走法與中國象棋'馬'的走法一樣，所以在8x8方格中用BFS即可。注意index轉換的問題。

	#include <cstdio>
	#include <queue>
	using namespace std;
	struct point_type{
	int i;
	int j;
	};
	const int direction[][2] = {{-2,-1},{-1,-2},{1,-2},{2,-1},{2,1},{1,2},{-1,2},{-2,1}};
	int BFS(point_type Start, point_type End)
	{
	int step[9][9] = {0};
	queue<point_type> Q;
	Q.push(Start);
	point_type cur, nxt;
	while (!Q.empty()) {
	cur = Q.front();
	Q.pop();
	if (cur.i == End.i && cur.j == End.j)
	return step[cur.i][cur.j];
	for (int i = 0; i < 8; ++i) {
	nxt.i = cur.i + direction[i][0];
	nxt.j = cur.j + direction[i][1];
	if (nxt.i < 1 || nxt.i > 8 || nxt.j < 1 || nxt.j > 8) continue;
	if (step[nxt.i][nxt.j] == 0) {
	step[nxt.i][nxt.j] = step[cur.i][cur.j] + 1;
	Q.push(nxt);
	}
	}
	}
	return step[cur.i][cur.j];
	}
	int main()
	{
	// freopen("input.txt","rt",stdin);
	char s1[3], s2[3];
	while (scanf("%s%s", s1, s2) != EOF) {
	point_type Start, End;
	Start.i = s1[0] - 'a' + 1;
	Start.j = s1[1] - '0';
	End.i = s2[0] - 'a' + 1;
	End.j = s2[1] - '0';
	int moves = BFS(Start, End);
	printf("To get from %s to %s takes %d knight moves.\n", s1, s2, moves);
	}
	return 0;
	}

view raw [UVa] 439 Knight Moves.cpp hosted with ❤ by GitHub