提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

目录

一：BFS算法的基础模版

    1.什么是BFS算法

    2.BFS代码的实现

二：剪枝的重要性

一：BFS算法的基础模板

1.什么是BFS算法

const int dir[4][2]={ {-1,0},{1,0},{0,-1},{0,1} };
for(int i=0;i<4;i++)
{
    int xx=x+dir[i][0],yy=y+dir[i][1];
}

红色部分是当前所在位置，蓝色部分是接下来可以跳的地方。

所以扩展到马的遍历，我们知道马走日字，所以就能很轻松写成

const int dir[8][2] = { {-1,2},{-1,-2},{1,2},{1,-2},{-2,1},{-2,-1},{2,1},{2,-1} };//分别对对应八个方向

有了以上基础，我们现在来分析题目，其实也没什么好分析的，赤裸裸的搜索题,只需要注意边界不超过就行，对于每个坐标组，我们可以利用STL的pair函数，或者使用结构体。这里我就没有用结构体了，下面给出代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MAXN 
int vis[500][500];
int ans[500][500];
const int dir[8][2] = { {-1,2},{-1,-2},{1,2},{1,-2},{-2,1},{-2,-1},{2,1},{2,-1} };//分别对对应八个方向
//int dx[8] = { -1,-2,-2,-1,1,2,2,1 };
//const int dy[8] = { 2,1,-1,-2,2,1,-1,-2 };//8个方向
int n, m, x, y;
queue<pair<int,int>> que;//pair将两个值合成一组数值组，方便操作
int main()
{
	memset(ans, -1, sizeof(ans));
	memset(vis, 0, sizeof(vis));
	cin >> n >> m >> x >> y;
	ans[x][y] = 0;
	vis[x][y] = 1;
	que.push(make_pair(x, y));//入队
	while (!que.empty())
	{
		int xx = que.front().first, yy = que.front().second;//取队首并删
		que.pop();
		//进行遍历
		for (int i = 0;i < 8;i++)
		{
			int u, v;
			u = xx + dir[i][0];
			v = yy + dir[i][1];
			//u = xx + dx[i];v = yy + dy[i];
			//注意边界
			if (u<1 || v<1 || u>n || v>m || vis[u][v]) continue;
			//别忘了剪枝
			vis[u][v] = 1;
			//入队，准备下一次遍历
			que.push(make_pair(u, v));
			ans[u][v] = ans[xx][yy]+1;//下一次能跳到的格子步数要加1
		}
		
	}
	for (int i = 1;i <= n;i++)
	{
		for (int j = 1;j <= m;j++)
		{
			printf("%-5d", ans[i][j]);
		}
		printf("\n");
	}

}

BFS算法中，最灵魂的地方莫过于剪枝了，大多数题目不通过剪枝减去重复搜索部分都会导致TLE因为搜索本来就暴力。这是最需要优化的地方。在本题中，剪枝就是利用标记数组，将已经走过的格子标记已走，每次搜索时先判断是否走过。那既然讲到了剪枝，我们下面来讨论一个题目剪枝和不剪的区别。

二：剪枝的重要性

我们还是以洛谷的一道题目为例子

#P1162

对于这道题，剪枝和不剪枝代码都能过，但差距就不止一点了。我们上一组测试数据

20
0 0 0 0 1 1 1 0 0 0 0 1 1 1 0 0 0 0 0 0
0 0 0 0 1 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0
0 0 0 0 1 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0
0 0 0 0 1 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0
0 0 0 0 1 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0
0 0 0 0 1 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0
1 1 1 1 1 0 1 1 1 1 1 1 0 1 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 1 0 1 1 1 1 0 0 0 1 1 1
0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 1 1 1 0 0
0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 1 0 0 0 0
0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 1 0 0 0 0
0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 1 1 1 1 1
0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 0 0 0 0 1
0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 1 1 1 1 1
0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 1 0 0 0 0
0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 1 0 0 0 0
0 0 0 0 0 0 0 0 1 1 1 0 0 1 1 1 0 0 0 0

在没剪枝之前，代码运行的时间是

而在我进行了剪枝之后，时间是

不仅仅是时间优化了很多，对于空间的优化也很大。所以剪枝是做BFS题目必须要做的一个步骤，即便题目可能不剪枝也能过，但你不能保证所有题目都能过。尤其是在DFS的题目中。

对于本题的代码也给出来

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int vis[35][35];int n;
int ans[35][35];
const int dir[4][2] = { {-1,0},{1,0},{0,-1},{0,1} };
queue<pair<int,int>> que;
void bfs(int x,int y)
{
    que.push({x,y});
    vis[x][y]=1;
	while (!que.empty())
	{
        pair<int,int> a=que.front();
		que.pop();
		ans[a.first][a.second] = 2;
		for (int i = 0;i <4;i++)
		{
			int xx = a.first+dir[i][0], yy = a.second+dir[i][1];
			if (xx >= 0 && xx <= n + 1)
				if (yy >= 0 && yy <= n + 1)
					if (ans[xx][yy] == 0 && vis[xx][yy]==0) 
					{
						vis[xx][yy]=1;
						que.push({xx,yy});
					}
						

		}
	}

}
int main()
{
	cin >> n;
	for(int i=1;i<=n;i++)
		for (int j = 1;j <= n;j++)
		{
			cin >> ans[i][j];
		}
	bfs(0, 0);
	for (int i = 1;i <= n;i++) 
	{
		for (int j = 1;j <= n;j++)
		{
			printf("%d ",2-ans[i][j]);
		}
		printf("\n");
	}
		
	return 0;
}

大致模板都差不多，就是先将节点入队，并标记，判空进入循环，取出队首元素，删去队首，进行搜索操作，对于其限制条件进行判断，如果符合条件就将下一个节点入队。