知识铺垫
多的不想放太多，感觉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; } };
总结
① 记住常规情况下的实现逻辑和算法板子
算法实现的伪代码大致可以这种描述
具体来说了，我现在遇到的，需要加偏移量来探索4个、8个、或者12个方向的情况比较比较多，原原本本使用邻接表的倒是少了。
② 注意细节
在整个代码中，尽量不要出现重复名字的变量吧，有时候容易出现编译没有问题，但是逻辑是有问题的。然后注意，倘若是坐标点，一般是使用pair或者结构体存储，是需要具体的调用其中的数据的，不能直接拿着就用了。
③ 层序遍历和宽搜了，基本是一个思想了，遇到层序遍历的题，可以直接使用宽搜模拟了
