广搜模板题

首先，我们来看题：

我们要求：从给定的一个点A走到点B的最短路径，那么，要肿么做呢？

也许有同学想到了DFS(深度优先搜索)，但是，要注意：

这一道题不是让我们求能否从A到B，而是求A到B的最短路路径的长度！！！ 显然，用DFS来解决这道题就不适合，如果我们想要求最短路径，那就需要把所有可以走的方法全部跑一次，最后统计答案，取最小值——很明显，复杂度过高了。

此时，我们就要掏出另外一种搜索方式了：$BFS(Breath First Search)$——广度优先搜索。

它有别于深度优先搜索，它的核心思想是把一个点同时把所有的可走的方式走一次，接下再继续往后走……循环往复，如果有一个点到了终点，那就停止循环。

问题来了，如何实现呢？ 我们新建一个队列，把每次的状态往队列里塞，然后依次取出队列的头状态进行下一步的拓展。

(什么？你不知道什么是队列？)

而在之中，有一个很重要的性质：这个队列中点的状态中的点的时间一定是升序排列的！！！

因为我们前面的点拓展完了之后就会把它的时间加一然后重新放回队列里拓展，这就使得队列里的数一定是升序排列的。所以，我们只要遇到了第一个到达终点的状态，就可以快乐地输出了！

代码(实现看注释)：

#include <iostream>
#include <queue>

using namespace std;

int n , m , sx , sy; //n,m含义如题目所示， sx , sy 则是用来记录起点的变量，方便后文
int movex[] = {1,1,-1,-1,2,-2,2,-2}, movey[] = {2,-2,2,-2,1,1,-1,-1}; //因为是一个“马”的走法，所以我们可以新建一个数组来存储走法，简化代码
char map[200][200]; //我是地图！！！
bool vis[200][200]; //这是一个剪枝，作用后面解释

struct node //用一个结构体来存储当前点信息
{
	int x , y , t; //当前的位置x，位置y 和当前的时间t
}now , next_one; //分别是当前的状态和下一个拓展的状态
queue <node> q; //我是队列！

bool check (int x , int y) //为了防止运行过程中数组越界和剪枝，我偷懒(bushi)做了一个判断是否可以到达这一个点的位置
{
	return x>=1&&x<=m&&y>=1&&y<=n&&!vis[x][y]&&map[x][y]!='*';
}

int main()
{
	cin >> n >> m; //输入
	for (int i = 1 ; i <= m ; i++) //一定不要输反！！！
		for (int j = 1 ; j <= n ; j++)
		{
			cin >> map[i][j];
			if (map[i][j] == 'K') //如果当前输入的点是"K"，也就是起点，要记录下来，方便后续运行
				sx = i , sy = j;
		}
	
	now.x = sx; //起始点的x位置
	now.y = sy; //起始点的y位置
	now.t = 0; //起始点的时间？当然是0啦！
	q.push(now); //把它塞进队列
	
	while (!q.empty()) //重复到队列中没有可拓展的状态
	{
		now = q.front(); //取出状态
		q.pop();
		
		if (vis[now.x][now.y]) continue; //如果这个点之前已经被别人走过了，那么它的时间一定比别人晚（想想为什么）
		vis[now.x][now.y] = true; //标记这个点被走过了
		
		if (map[now.x][now.y] == 'H') //如果到达了终点，则可以输出
		{	
			printf("%d" , now.t);
			break;
		}
		
		for (int i = 0 ; i < 8 ; i++) //往八个方向拓展
			if (check(now.x+movex[i],now.y+movey[i])) //可以走
			{
				next_one.x = now.x+movex[i];
				next_one.y = now.y+movey[i];
				next_one.t = now.t+1;
				
				q.push(next_one);
			}
	}
	
	return 0;
}

也许你还有一个疑问： 既然在加入队列时，已经有了判断

if (check(now.x+movex[i],now.y+movey[i])) 为何在取出的时候还要再做一次判断？

if (vis[now.x][now.y]) continue; 因为在这个点拓展之后，说不定这个点也被别人同时拓展了，虽然两者时间一样，但是没有必要重复加入队列了，对答案没有任何影响。 第一次写题解，希望大家多多包容！