1936_Knight_Moves

题目链接：

http://soj.me/1936

题目大意： 给出一个8×8的棋盘，骑士走的是“日”字型，给出骑士的初始位置和目标位置，问最少经过多少步可以到达目标位置。

思路： 比较简单的宽度优先搜索题目，只要从起始位置开始，每一步搜索完这一层能够达到的所有点，这样你能保证第一次找到目标点的话就一定是最少的步数到达的。

代码：

#include <iostream>#include <queue>using namespace std;int move_x[8] = { -1, -2, -2, -1, 1, 2, 2, 1 };int move_y[8] = { -2, -1, 1, 2, 2, 1, -1, -2 };bool visited[8][8];class Point {public:	int x;	int y;	Point(int xx = 0, int yy = 0) {		x = xx;		y = yy;	}};Point target;int bfs(const Point &start);bool checkPoint(const int x, const int y);int main() {	int numTestcases;	cin >> numTestcases;	while (numTestcases--) {		string a, b;		cin >> a >> b;		Point start = Point(a[1] - ‘1‘, a[0] - ‘a‘);		target.x = b[1] - ‘1‘;		target.y = b[0] - ‘a‘;		for (int i = 0; i < 8; ++i) {//每次重置整个棋盘未被访问			for (int j = 0; j < 8; ++j) {				visited[i][j] = false;			}		}		cout << "To get from " << a << " to " << b << " takes " << bfs(start)				<< " knight moves." << endl;	}	return 0;}int bfs(const Point &start) {	visited[start.x][start.y] = true;	if (start.x == target.x && start.y == target.y)		return 0;	else {		int numMoves = 1;		queue<Point> cur, next;//next装下一层可以到达的点		cur.push(start);		while (!cur.empty()) {//下一层还有点可以访问到			while (!cur.empty()) {//将当层所有点能到达的点放到下一层				for (int i = 0; i < 8; ++i) {					Point p = Point(cur.front().x + move_x[i],							cur.front().y + move_y[i]);					if (p.x == target.x && p.y == target.y) {						return numMoves;					} else if (checkPoint(p.x, p.y)) {						next.push(p);						visited[p.x][p.y] = true;					}				}				cur.pop();			}			while (!next.empty()) {//将下一层的点设置为当层的点，准备下一轮操作				cur.push(next.front());				next.pop();			}			numMoves++;		}		return numMoves;	}}bool checkPoint(const int x, const int y) {//判断一个点是否可以访问	if (x >= 0 && x < 8 && y >= 0 && y < 8 && !visited[x][y])		return true;	else		return false;}

Sicily 1936. Knight Moves 解题报告