蓝桥杯算法竞赛备考（一）——搜索专题（下）

还有一个问题，我们在使用BFS时会设一个inq数组记录结点有没有入队，为什么不是记录结点有没有访问呢，不知道小伙伴们想没想过这个问题。
区别在于，设置成结点是否已访问，会导致有些点在队列中但是还没有被访问，由于其他结点可以到达它而将这个结点入队，导致很多结点重复入队，这是很不明智的。

以后也会专门出一篇讲解比赛中常用的STL标准模板库。
上面对BFS的讲解参考胡凡《算法笔记》并补充了自己对BFS的理解。

题目分析
该题是要求从起点到终点的最小步数。我们可以有两种解决方案，DFS和BFS。

可以DFS所有从起点到终点的所有路径，然后取路径最短的那条。BFS是很理所当然的，因为求的是最小步数，涉及最短问题。

我们先来看一下BFS该如何解决这个问题。因为是板子题嘛直接照着模板敲就好了~

AC代码（BFS）

//bfs 广度优先搜索//迷宫问题 求解最短路径#include #include using namespace std;const int N = 100;int n, m;//n行m列char maze[N][N];//迷宫bool inq[N][N];//记录位置(x,y)是否入队int x[4] = {-1, 1, 0, 0};//增量数组int y[4] = {0, 0, -1, 1};struct node{ int x, y; int step;}s, t, Node;//s起点 t终点 Node临时节点bool test(int x, int y)//判断位置(x,y)是否有效{ //以下三种情况不能入队 if (x >= n || x < 0 || y >= m || y < 0) return false;//出界 if (maze[x][y] == '*') return false;//墙壁 if (inq[x][y] == true) return false;//已入队 return true;//其余情况可以将该点入队}int bfs(){ queue q;//定义队列 q.push(s);//将起点入队 while(!q.empty())//队列不为空执行 { node top = q.front();//取出队首元素 q.pop();//出队 //inq[s.x][s.y] = true;//将起点设为已入队 if (top.x == t.x && top.y == t.y)//到达终点 { return top.step;返回终点的层数，即最少步数 } for (int i = 0; i < 4; i++)//枚举四个方向 { int newX = top.x + x[i]; int newY = top.y + y[i]; if (test(newX, newY))//下一个点合法 { Node.x = newX; Node.y = newY; q.push(Node);//将该点入队//或q.push((Node){newX,newY}); Node.step = top.step + 1;//层数加1 inq[newX][newY] = true;//标记成已入队 } } } return 0;}int main(){ cin >> n >> m; for (int i = 0; i < n; i++) { getchar();//过滤掉每行的换行，不加这句是不能AC的 for (int j = 0; j < m; j++) { maze[i][j] = getchar();//读入数据 } } cin >> s.x >> s.y >> t.x >> t.y; s.step = 0; cout << bfs() << endl; return 0;}

我们再来看一下如何用DFS来解决这个问题。用DFS搜索出所有可以从起点到终点的路径，并记录步数。DFS函数记录当前搜索的点的坐标(x,y)和所用步数step。用一个变量minsize更新最小步数minsize = min(minsize, step)。其余的操作其实和上一篇文章的迷宫问题求方案数是差不多的啦。小伙伴们还是不懂的话可以去看前一篇文章呀~

AC代码（DFS）

#include #include

对上述代码做几点说明

里面用到了STL中的pair。当想要将两个元素绑在一起作为一个元素时，又不想因此定义一个结构体，那么就可以用pair这个小玩意啦~pair里面有两个元素，类型是可以自定义的，分别是first,second。
*要注意minsize初始化要大一些，这样才能更新最小。
*DFS求解最短路问题是没有优势的。显而易见，DFS会搜索所有的路径，然后求出最小步数，搜索了很多无效状态，效率是非常低的，很容易就TLE。

题目分析
这道题其实和前面那一道很相似，前面那一道是求从起点到终点的最短步数，而这道是求从起点(马的位置)到各个点(棋盘各个点)的最短步数。
那么该怎么办呢~很简单，从马的位置点(x, y)开始BFS，用一个ans数组来记录起点到达各个点时的层数，也就是最短步数。最后输出ans即可。
题目本身的思路还是很好想滴~还是有些地方需要注意一下。

一个马可以走的位置已经用圆圈圈住啦~八个偏移量(-2,1),(-2,-1),(-1,2),(-1,-2),(2,1),(2,-1),(1,2),(1,-2)。我们可以用方向数组来表示：

int dx[8]={-2,-2,-1,-1,2,2,1,1};int dy[8]={1,-1,2,-2,1,-1,2,-2}; 输出格式要求左对齐，宽5格。

printf("%-5d", ans[i][j]);cout<

第二个cout的写法大家可以试一试可不可以通过，这是我在洛谷题解里面找到的。还是推荐第一种printf的写法。

像一些方向数组，初始化数组等一些小技巧小伙伴们要好好整理一下噢，可以提高代码的效率和简洁性。

AC代码

#include #include #include #include #include using namespace std;const int N = 450;int n, m;int ans[N][N];//储存到达每点的最少步数bool inq[N][N];//标记是否已入队int dx[8]={-2,-2,-1,-1,2,2,1,1};int dy[8]={1,-1,2,-2,1,-1,2,-2};//坐标偏移量struct node{ int x; int y;}s, Node;bool check(int x, int y){ if (x <= 0 || x > n || y <= 0 || y > m) return false;//出界 if (inq[x][y] == true) return false;//已入队 return true;}void bfs(){ queue q; q.push(s);//起点入队 inq[s.x][s.y] = true;//标记起点已入队 while(!q.empty()) { node top = q.front(); q.pop(); for (int i = 0; i <= 7; i++) { int newx = top.x + dx[i]; int newy = top.y + dy[i]; if (check(newx, newy)) { Node.x = newx; Node.y = newy; q.push(Node); //(Node.x,Node,y)的层数就是队头层数+1，即最短步数。 ans[Node.x][Node.y] = ans[top.x][top.y] + 1; inq[Node.x][Node.y] = true;//标记已入队 } } }}int main(){ memset(ans,-1,sizeof(ans));//将ans数组都设为-1 cin >> n >> m >> s.x >> s.y; ans[s.x][s.y] = 0; bfs(); for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { printf("%-5d", ans[i][j]); } printf("n"); } return 0;}

当然为了节省空间这道题也可以只开一个ans数组。来记录最少步数和是否已入队。

ans[x][y] != -1说明(x,y)点已入队；ans[x][y] == -1说明(x,y)点未入队。
具体代码这里就不再赘述了噢~

题目分析

这道题貌似有个名字叫连通块问题。

这道题难了我好长时间，我觉得有些小伙伴肯定也会在这道题上卡一下。主要是题目意思有点难理解。我开始的时候以为块是只十字架结构的1，也就是1的上下左右都是1，然后这些1构成的就是一个块。然后看样例发现块数不太对。样例是4块。

经过长时间的绞尽脑汁的琢磨（原谅我的菜）,我才明白块说的是从某个1开始，看它的上下左右有没有1，有1的话就在看这些1的上下左右有没有1，依次类推，直到找不到1为止。这么说呢可能小伙伴们还是不太懂，那么我们举个例子吧~

样例中的四块是用圆圈圈住的这四个。以最上面的那个为例，从最左边的1开始搜索，它的右边有1个1。这个1的右边和下边有1。这些1的上下左右就没有新的1了。因此这些1组成一个块。说到这大家应该明白了许多hh~。

我们还可以发现单独的1也可以是一个块，不然这题答案就是3了。
理解了题意，思路也就很好想了。我们可以BFS某个1，找出与它符合块条件的所有1，通过BFS将这些1标记下来，进而可以不重复的搜索块的个数。

AC代码

#include #include #include

BFS的做法相对来说还是比较固定的，所以注释有些重复的简单的我就不再写了。
大家可以尝试用DFS来做一下这道题噢~ 一道题用不同的解法才能看出算法的魅力！
DFS解答的代码我放在了这里噢~

记忆化搜索的目的就是为了解决重复计算。

通过一个斐波那契数列和小伙伴们来聊一聊什么是记忆化搜索吧~

Answer1、递归实现
斐波那契数列的递归实现是比较简单的。就抓住递归的边界和递归式就没问题了。

#include using namespace std;int n;int fib(int n){ if (n == 1) return 0; if (n == 2) return 1;//递归边界 return fib(n - 1) + fib(n - 2);//递归式}int main(){ cin >> n; for (int i = 1; i <= n; i++) { cout << fib(i) << ' '; } cout << endl; return 0;}

递归的时间复杂度是成指数级增长的，因此如果不进行一些优化的话，求解的N很大的话，很容易就TLE。我们可以看出fib(3)被重复计算了两次，如果我们将这个数保存起来，再遇到的时候就可以直接使用，大大简化了计算量。这就是记忆化搜索的思想。
Answer2、记忆化搜索

#include using namespace std;const int N = 50;int n;int instance[N];//判断某个状态是否算出过解int dfs_m(int n){ if (n == 1) return 0; if (n == 2) return 1;//递归的边界条件 if (instance[n]) return instance[n];//某个状态出现过就直接输出该状态的解 return instance[n] = dfs_m(n - 1) + dfs_m(n - 2);//没算出过解就按递推式正常算}int main(){ cin >> n; for (int i = 1; i <= n; i++) { cout << dfs_m(i) << ' '; } cout << endl; return 0;}

记忆化搜索按照自顶向下的顺序，每求得一个状态时，就把它的解保存下来，以后再次遇到这个状态时就不用重复求解了。

记忆化搜索包含两个要素记忆化和搜索。

沿用搜索的一般模式，本质还是用递归函数实现。在搜索的过程中将已经得到的解保存起来，下次需要时直接用。

记忆化搜索是理解DP思想很重要的基础噢，把记忆化搜索掌握明白，会很容易就入门动态规划噢~

还有一种递推的方法，时间复杂度只有 O ( n ) O(n) O(n)。递推和递归的区别在于，递推是自底向上，递归是自顶向下。

Answer3、递推法

#include using namespace std;const int N = 50;int n;int ans[N];int main(){ cin >> n; ans[1] = 0; ans[2] = 1; for (int i = 3; i <= n; i++) { ans[i] = ans[i - 1] + ans[i - 2];//递推式 } for (int i =1; i <= n; i++) { cout << ans[i] << ' '; } cout << endl; return 0;}

美好的时光总是短暂的，今天的算法学习就要告一段落了。搜索是蓝桥杯的基础中的基础，小伙伴们一定要好好学噢~。下篇文章初步计划是要讲下蓝桥杯涉及到搜索的真题，小伙伴们可以期待一下噢。
蓝桥杯系列在省赛前我会一直更新下去的。什么？你还不知道省赛是什么时候，4月9就要比赛啦！小伙伴们也要抓紧时间学习啦。我们下一期再见吧~
小伙伴们一键三连支持一下吧，绝对不会让你们失望的。

由于我水平有限可能一些地方讲的不清楚或者不对，都欢迎小伙伴们给我提建议噢，私信我看到的话一定会回的。