目录
💓前言
BFS和DFS一样了，都是搜索界中独占一片天下的地位，但是可能有小伙伴感觉捋不清其执行的逻辑，本文主要是结合两种常见的刷题模式来演示怎么系统的拿捏住常规的宽搜的算法模板。
💓知识铺垫
多的不想放太多，感觉BFS和DFS一样，知识点了，就这么一点，但是它的题，真的挺多的，与其看概念，不如直接去磕题了，浅放一张英雄哥的知识总结吧。
今天的题是BFS，但是今天的每日一题要探索的点比较多，有12个，先用另外一个简单一点的BFS来熟悉一下，再解决今天的题吧。
💓例一、 P1443 马的遍历
BFS模板💒题目描述
🌟解题报告
确实是传统的bfs的实现流程。相比于常规的，只是说，从四个方向变成了八个方向。然后在我现在做的题里，除了迷宫那个题，在确定偏移量数组的时候需要依据方向，其他情况下了，其实都可以，我现在默认的顺时针安排也是没有问题的，草稿纸上画的时候，不要画得太凌乱，不然不好数。
想记录的第二个点了，就是坐标点存储可以能用结构体直接就用结构体吧，不必搞得很妖艳，能Ac就是最好的。
bfs的题都有一个特点吧，姑且来说，就是到达某个点，最少要多少步，可达性的最短路了。
bfs的流程：
1、将当前传入bfs的坐标标记为使用过了，放入队列中
2、当队列不空的时候进入循环
3、取出当前队列的队头，待会拓展它
4、去除这个使用过的队头
5、结合偏移量数组枚举现在有点方向
6、遇到不合法的就跳过
7、将合法的，没有探索过的点加入队列，标记使用过了
🌻参考代码(C++版本）
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 410;
int n,m,x,y;
//偏移量数组，自己草稿纸上画一下就好
int dx[] = {1,2,2,1,-1,-2,-2,-1};
int dy[] = {2,1,-1,-2,-2,-1,1,2};
bool st[N][N];//记录当前的点的探索状态
int dist[N][N];//记录(x,y)到各个点之间的距离
typedef pair<int, int> PII;
//用结构体也是可以的
// struct node{
// int x,y;
// };
void bfs(int x,int y)
{
queue<PII> q;
// queue<node> q;
q.push({x,y});
//标记(x,y)这个点已经走过了
st[x][y] = true;
//更新(x,y)到达点(x,y)的距离
dist[x][y] = 0;
//当队列不空
while(q.size())
{
//取出队头
auto hh = q.front();
//去除用过的队头
q.pop();
//使用当前的队头，去探索能够到达的方向，这儿是八个
for(int i = 0; i < 8;i++)
{
int xx = hh.first + dx[i];
int yy = hh.second + dy[i];
//判断当前探索出来的队头，是否合法
if(xx < 1 || xx > n || yy < 1 || yy > m) continue;
//如果当前的点合法，而且没有探索过，就去探索它
if(st[xx][yy] == false)
{
q.push({xx,yy});
st[xx][yy] = true;
//更新到达当前点的最短距离
dist[xx][yy] = dist[hh.first][hh.second] + 1;
}
}
}
}
int main()
{
cin >> n >> m >> x >> y;
memset(dist,-1,sizeof dist);
bfs(x,y);
//遍历经过bfs之后，(x,y)到达棋盘各个位置需要最少的步数
for(int i = 1; i <= n;i++)
{
for(int j = 1; j <= m;j++)
printf("%-5d",dist[i][j]);
printf("\n");
}
return 0;
}
💓例二、 P1747 好奇怪的游戏
💒题目描述
🌟解题报告
其实玩法和上面的马的遍历差不多，只是说，当探索到(1,1)这个点之后，就要记录答案，结束搜索了。
然后搜索的流程就是上面第一题中我用红色字体备注出来的部分，多敲几遍其实就可能背得下来了。
想浅记一下需要注意的点：
一般取出队头以后，它是一个结构体或者是一个pair，存储在其中的坐标(x，y)是需要通过.运算符来获取的，切忌直接夸夸夸用x和y去更新新的点，编译不会报错，因为整个代码中确实有x和y，但是因为逻辑是错的，所以大概率是没有结果的🌻参考代码(C++版本)
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 30;
int a1,b1,a2,b2,ans;
//自己草稿本上画了
int dx[] = {1,2,2,2,2,1,-1,-2,-2,-2,-2,-1};
int dy[] = {2,2,1,-1,-2,-2,-2,-2,-1,1,2,2};
int dist[N][N];
bool st[N][N];
struct node
{
int x,y;
};
void bfs(int x,int y)
{
memset(dist,-1,sizeof dist);
memset(st,0,sizeof st);
queue<node> q;
q.push({x,y});
st[x][y] = true;
dist[x][y] = 0;
//标准的取队头，拓展队头
while(q.size())
{
auto hh = q.front();
q.pop();
//到达(1,1)
if(hh.x == 1 && hh.y == 1)
{
ans = dist[hh.x][hh.y];
return ;
}
//探索能够到达的方向
for(int i = 0; i < 12;i++)
{
int xx = hh.x + dx[i];
int yy = hh.y + dy[i];
//判断探索的结果是否合法
if(xx > 0 && xx <= 20 && yy > 0 && yy <= 20 && !st[xx][yy])
{
st[xx][yy] = true;
dist[xx][yy] = dist[hh.x][hh.y] + 1;
q.push({xx,yy});
}
}
}
}
int main()
{
cin >> a1 >> b1 >> a2 >>b2;
bfs(a1,b1);
cout << ans << endl;
ans = 0;
bfs(a2,b2);
cout << ans << endl;
return 0;
}
💓例三、 LCP 44. 开幕式焰火
💒题目描述
🌟解题报告
遍历树(本质也就是结构体+指针)+使用哈希表的思想统计个数。可以使用BFS搜吧，但是我想放过自己，能Ac就好。
🌻参考代码(C++版本)
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> cnt = vector<int>(1010,0);
void pre_dfs(TreeNode* root)
{
if(root)
{
cnt[root->val]++;
if(root->left) pre_dfs(root->left);
if(root->right) pre_dfs(root->right);
}
return ;
}
int numColor(TreeNode* root) {
//树的前序遍历+哈希表思想
pre_dfs(root);
int ans = 0;
for(int i = 0; i < cnt.size();i++)
if(cnt[i]) ans++;
return ans;
}
};
💓例四、 102. 二叉树的层序遍历
💒题目描述
🌟解题报告
层序遍历本来也就是结合BFS进行的吧。层序遍历是先处理结根点，同时了，倘若有左右孩子，就将左右孩子入队，因此能够从上而下，逐层打印。按照这种先处理当前层的根节点，再处理下一层的叶子结点，也就是BFS的一层一层搜索的思想不谋而合了。
那就直接砸宽搜的板子吧，先将最开始的根节点root入队，在队列不空的情况下进行取队头、拓展队头、更新入队信息的操作。🌻参考代码(C++版本)
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
//这个倒是确实是宽搜的板子了
vector<vector<int>> ans;
queue<TreeNode*> q;
//在队列不为空的时候入队。
if(root != nullptr) q.push(root);
//当队列不为空的时候，模拟一层一层的宽搜
while(q.size())
{
//获取当前这层入队的数量，待会要逐一的探索它们
int n = q.size();
vector<int> tmp;
for(int i = 0; i < n;i++)
{
//获取队头信息
auto hh = q.front();
q.pop();
//也是使用队头去拓展
tmp.push_back(hh->val);
if(hh->left) q.push(hh->left);
if(hh->right) q.push(hh->right);
}
//统计一层搜索出来的结果
ans.push_back(tmp);
}
return ans;
}
};
💓例五、 1609. 奇偶树
💒题目描述
🌟解题报告
和上面一个题一样，看到层序遍历，其实就向着BFS的方向思考就好，和上面一个题换汤不换药了，按照题目意思模拟出来就好。
唯一需要注意的了，因为有升序、降序的要求，所以需要存储前驱结点的数据，但是倘若现在的处理根roo = 1的左子树 = 10d的情况，也就是它前面看起来是没有前驱结点的，所以这就需要我们初始化前驱结点。比如对于要递增的，就初始化为一个小于数据范围的数，比如我这里的-1，假如是递降的，就初始化一个大于数据范围的数，比如我这里的1e6+10
int pre_val = (level%2 == 0) ? -1 : 1e6 + 10;🌻参考代码(C++版本)
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
bool isEvenOddTree(TreeNode* root) {
//一层一层的搜，然后按照题目要求进行判断
queue<TreeNode*> q;
if(root != nullptr) q.push(root);
int level = 0;
while(!q.empty())
{
//计算现在队列存的当前这层的元素个数
int n = q.size();
//初始化待会用于比较的前驱值
//倘若是再偶数下标层,初始化为-1
//倘若是在奇数下标层，初始化10^6+10
int pre_val = (level%2 == 0) ? -1 : 1e6 + 10;
for(int i = 0;i < n;i++)
{
auto hh = q.front();
q.pop();
//偶数下标层的节点值都为奇数，严格递增
//奇数下标层的节点值都是偶数，严格递减
//因为要比较，所以需要当前队列首的前一个元素的信息
int now_val = hh->val;
if(level % 2 == 0 && (now_val)%2 == 0 || level % 2 && now_val%2) return false;
//不满足偶数下标递增，以及奇数下标递减
if((level % 2) == 0 && now_val <= pre_val || (level % 2) && now_val >= pre_val) return false;
//更新前驱结点信息
pre_val = now_val;
//将新的信息放入队列的环节
if(hh->left) q.push(hh->left);
if(hh->right) q.push(hh->right);
}
level ++;//处理完成一层，进入下一层
}
return true;
}
};
还有一个推箱子的题，感觉暂时拿捏不住，不想磕它了，1263. 推箱子。等后面找个机会二刷吧
原题传送门
💓 总结
① 记住常规情况下的实现逻辑和算法板子
算法实现的伪代码大致可以这种描述
具体来说了，我现在遇到的，需要加偏移量来探索4个、8个、或者12个方向的情况比较比较多，原原本本使用邻接表的倒是少了。
② 注意细节
在整个代码中，尽量不要出现重复名字的变量吧，有时候容易出现编译没有问题，但是逻辑是有问题的。然后注意，倘若是坐标点，一般是使用pair或者结构体存储，是需要具体的调用其中的数据的，不能直接拿着就用了。
③ 层序遍历和宽搜了，基本是一个思想了，遇到层序遍历的题，可以直接使用宽搜模拟了
