当前位置：首页 > ops >正文

蓝桥杯算法之搜索章 - 6

ops 2025/8/19 9:03:57

大家好，接下来我将接着BFS的相关内容继续讲解。

将前面的BFS收尾一下

后续将更新多源BFS的内容！

前言

一、题目1

二、Catch That Cow S

题目展示：

思路分析：

代码实现：

三、八数码难题

题目展示：

思路分析：

代码实现：

总结

前言

在搜索章 - 5里面，我们大概了解了bfs的搜索是如何通过队列来实现的。

接下来将再次带来两道题让我们再度理解一下前面的内容。

一、题目1

P1588 [USACO07OPEN] Catch That Cow S - 洛谷

P1379 八数码难题 - 洛谷

大家有兴趣可以自己先行做一下

二、Catch That Cow S

题目展示：

思路分析：

看了这道题，我们会发现要求我们求出最小步数。我们就可以往宽度优先搜索上面去思考的。

通过题目告知的三种走法，我们可以想到我们之前写的马的遍历那道题，马可以往八个方向跳。

这里也可以想成三种方法走

我们在通过队列实现宽度优先搜索，通过记录得到每个位置的最小步数。

如何让这里的三种走法走起来呢？

通过队列存放位置的坐标，我们拿到对头元素坐标，通过这个来计算一下新的坐标在哪里就行。

首先判断坐标的正确与否，再判断对应坐标是否被走过，被走过就代表了已经有最小步数

如何存放不同坐标的最小步数呢？

使用一个数组即可：dist[N]，dist[i]代表到达i位置的最小步数。

如何填入更新最小步数呢？

通过前一个坐标的dist[i]再加上1就是当前坐标处的最小步数

多组测试数据需要清理吗？

都是从不同的x位置到达不同的y位置，最小步数的数组dist需要清理

如何确定BFS的结束呢？

当位置到达对应的y的时候，并且已经更新完最小步数之后就可以直接退出了

代码实现：

#include <iostream>
#include <queue>
#include <cstring> //memset的头文件
using namespace std;
const int N = 1e5 + 10;//定义数据范围
int dist[N];//dist[i]表示到达i号位置最短步数 
int x, y;
int n = 1e5;//边界判断，避免超出了最远处
void bfs()
{queue<int> q;q.push(x);dist[x] = 0;//x位置处最小步数为0while(q.size()){int t = q.front(); q.pop();//从t位置走-1 ， 1 ， i * 2int a = t + 1, b = t - 1, c = t * 2;//更新位置//判断位置是否合法，位置是否没有被走过if (a <= n && dist[a] == -1){dist[a] = dist[t] + 1;q.push(a);}if (b >= 1 && dist[b] == -1){dist[b] = dist[t] + 1;q.push(b);}if (c <= n && c >= 1 && dist[c] == -1){dist[c] = dist[t] + 1;q.push(c); }//如果更新的位置到达了y就结束if (a == y || b == y || c == y) return;//代表已经到达了 }
}
int main()
{int T; cin >> T;while(T--){memset(dist, -1, sizeof(dist));cin >> x >> y;bfs();cout << dist[y] << endl;}return 0;
}

这道题大家也可以去采取一下dfs实现，但是会经过很多的重复位置，要记得使用记忆化搜索来减少递归~

三、八数码难题

题目展示：

思路分析：

看到这个题目大家可能会有点懵，该怎么做呢？

我先讲一下如何将二维坐标和一维坐标的转换

对于一个从(0, 0)开始的n * m的二维数组

对应的(x, y)坐标转换成一维的是：int pos = x * m + y;

从一维坐标转二维坐标：int x = pos / m;

int y = pos % m;

至于是为什么，大家可以画一个二维数组的图来分析，我们只是统计该二维坐标之前有多少个值，将这个值变成我们的一维坐标来进行的。

我们有了这个之后，就有了一个大的方向：

通过string去接收字符串

通过上下左右走动，就可以计算走动后的新二维坐标，将对应的一维坐标算出来，然后通过string容器去使用swap交换两个一维的字符，来代表进行了一次交换。

这样我们就有了新状态的字符串，更新它的最小形成的次数，将新状态的字符串放进队列去。

如何记录每个字符串形成的最小次数呢？

通过一个哈希表：unordered_map<string, int>就可以去记录了

如何确定结束呢？

将更新后的字符串和目标字符串比较一下，如果相同就直接结束即可

如何让二维坐标走动呢？

通过偏移量数组dx[],dy[]实现

代码实现：

#include <iostream>
#include <queue>
#include <string>
#include <unordered_map>
using namespace std;
unordered_map<string, int> mp;//到达这个字符串的最小步数 
string aim = "123804765";
string t;
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
void bfs()
{queue<string> q;q.push(t);while(q.size()){string ret = q.front(); q.pop();int pos = 0;while(ret[pos] != '0') pos++;int i = pos / 3, j = pos % 3;//计算空格对应的二维坐标for (int k = 0; k < 4; k++)//由于会出现和上下左右都交换，所以要用循环去走一下{//计算要交换的棋子的二维坐标 int x = i + dx[k];int y = j + dy[k];if (x > 2 || x < 0 || y > 2 || y < 0) continue;int tmp = x * 3 + y;//计算它的一维坐标 string next = ret;//避免ret被修改swap(next[tmp], next[pos]);if(mp.count(next)) continue;//如果有了最小次数 mp[next] = mp[ret] + 1;q.push(next);if (next == aim) return;}}
}int main()
{cin >> t;bfs();cout << mp[aim] << endl;return 0;
}