[数据结构与算法]UVA 439 Knight Moves 解题报告

广度优先搜索（BFS）

????????广度优先遍历也叫广度优先搜索，广度优先搜索从某个顶点出发，访问顶点，然后访问该结点的所有未被方位的邻接点，直到结点不存在未被访问的邻接点。

? ? ? ? 其算法步骤一般为：1、将起点入队；2、分析队首元素；3、将队首结点可拓展的点入队。如果队首结点没有可拓展的点，将队首结点出队，重复步骤，直到达到目标位置或者队列为空。

简单分析：

? ? ? ? 这是个简单的训练题，题意不需要解释。我在做的时候，将紫书上的棋盘横放下来观察，即字母表示行，数字表示列，且棋盘数组下标范围是1~8。

? ? ? ? 棋子不能走到已经走过的位置，否则一定不是最短路线。

? ? ? ? 另外，棋子在一个点可以走八个位置，我就用一个for循环和pacex、pacey数组模拟走棋的八种情况，然后进行检验是否越界或已经走过。

? ? ? ? 最后BFS，输出结果。

我的代码：

#include <iostream>       // Uva 439
#include <queue>
#include <cstring>
using namespace std;

struct Point
{
	int x, y;
	int step;
};
queue<Point> kaede;
bool flag[9][9] = { true };   // 走过的点不再走，否则肯定不是最短的
string start, finish;
int pacex[8] = { 1,2,2,1,-1,-2,-2,-1 };   // 八个方向的横坐标
int pacey[8] = { 2,1,-1,-2,-2,-1,1,2 };   // 八个方向的纵坐标

void BFS(Point now, int& finishx, int& finishy) 
{
	while (!kaede.empty())
	{
		if (kaede.front().x == finishx && kaede.front().y == finishy)
		{
			cout << "To get from " << start << " to " << finish << " takes " << kaede.front().step << " knight moves." << endl;
			break;
		}
		
		for (int i = 0; i < 8; i++)
		{
			Point site;
			site = now;      

			site.x += pacex[i];
			site.y += pacey[i];
			site.step = now.step + 1;
			if (site.x > 8 || site.x <= 0 || site.y > 8 || site.y <= 0 || flag[site.x][site.y] == false)   //若越界或已标记，continue；
				continue;
				
			kaede.push(site);  // 规范移动，就压入队列；
			flag[site.x][site.y] == false;  // 将该点标记，以后不再走到这一点
		}
		kaede.pop();
		now = kaede.front();    // now表示队首元素
	}
}

int main()
{
	while (cin >> start >> finish)
	{
		memset(flag, true, sizeof(flag));
		while (!kaede.empty())
			kaede.pop();
		// 转换坐标
		int startx = start[0] - 'a' + 1, starty = start[1] - '0';
		int finishx = finish[0] - 'a' + 1, finishy = finish[1] - '0';
		Point init;  
		init.x = startx, init.y = starty, init.step = 0;    // 初始化起点
		flag[startx][starty] = false; // 初始位置标记，以后不再走过这个点
		kaede.push(init); // 将起点压入队列
		BFS(init, finishx, finishy);  // BFS
	}
}

加油，继续努力，通过紫书学习各种算法、磨练代码能力。