DFS/BFS入门及深入推荐题目及心得整理
DFS/BFS的入门推荐题目及心得整理
前言：以上为我早期学习图论的一些做题笔记和心得，一边学习Acwing，一边在洛谷codeforces上刷题，所以笔记有一些是借鉴大佬们的题解思路理解的，因为此篇笔记历史悠久，一些题解未能附加出处，在此致歉。
此篇笔记 包含了 DFS/BFS的定义和大致题型的介绍，简单的变式拓展题目推荐，希望可以给刚开始准备接触图论的同学提供到帮助。
也可以看做一个题单？
文章目录
- DFS/BFS的入门推荐题目及心得整理
- <一> DFS/BFS
- 1. DFS简介 + 全排列搜索/避免全排列
- 2. DFS中的连通性和搜索顺序
- 3. DFS剪枝搜索
- 4.DFS洛谷题
- 5. BFS简介
- 6. BFS中的Flood Fill和最短路模型
- 7.多源BFS
- 8.最小步数模型
- 9. BFS洛谷题
- 10. DFS+BFS拓展
<一> DFS/BFS
1. DFS简介 + 全排列搜索/避免全排列
DFS定义：搜一棵树，尽量往深搜，递归搜到尽头再返回
由于DFS是基于系统栈的递归，所以可能会爆栈
如果出现了RE错误，很有可能就是爆栈了，递归死循环。
DFS重点：回溯，剪枝，构造
全排列：
来源：acwing 842.排列数字
类似：P3623 枚举排列
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 10; int n , path[N];// 记录答案的数组 bool st[N]; // 状态数组，标记当前位置是否走过 void dfs(int u ) // 当前需要填写的位置，第几个数字 { if(u == n){ // 递归到最后一个数字结束 for (int i = 0; i < n; i ++ ) cout << path[i] << ' '; // 输出保存的结果 puts(" "); } if(u>m)return; for (int i = 1; i <= n; i ++ ) if (!st[i]) // 没有被用过的数 { //恢复现场的部分就是 【回溯】 path[u] = i ; st[i] = true; // i被用过 dfs(u + 1);// 走到下一层 st[i] = false;//递归结束的时候恢复现场，恢复到递归前状态 path[u] = 0;//恢复现场，但是这道题特殊，因为每次path[u]都会被覆盖，所以这一条写不写都行 } } int main(){ cin >> n;dfs(0);return 0 } 非全排列：
来源：P1460 [USACO2.1]健康的荷斯坦奶牛 Healthy Holsteins
for(int r=path[u-1]; r<=a; r++) //这里很重要，决定了是80分还是100分 //遍历的起点从上一次的编号开始，这样可以避免：1-2-3 和 1-3-2 ， 2-1-3 ， 2-3-1 ， 3-1-2， 3-2-1的重复查找 //这些重复的选择里面字典序最小的（1-2-3）会被第一个搜出来，其他重复的选择我们不需要，直接不看，这就让某两个TLE的测试点AC了 if(!st[r]) //这个点没有被标记过 { path[u] = r; //存进路径 st[r] = true; //标记 dfs(u+1); //递归找下一层 st[r] = false; //回溯 path[u] = 0; //回溯 } - 区别主要在dfs函数的for循环的上界和下界
2. DFS中的连通性和搜索顺序
2.1 关于DFS是否需要恢复现场的问题：
我的理解是：
如果搜索的是一个图内部的点，每个点被搜索到之后状态在之后也无需改变，不需要恢复什么dfs对结点的操作。
【比如判断两个点是否联通，每个结点只需要走一次，只需要打上st[ ]标记，这个就算恢复了也是重新和第一次到这个结点一样搜索，没有区别，无需恢复。】
如果搜索的是一个外部的宏观角度，这个图内部不同情况对应整个图的一个新状态
【如八数码】【如全排列】【如记录搜索路径】是否恢复会影响到算法，则需要恢复。
tips：
如果不做任何恢复现场的操作，在每次结束调用某个函数的时候，系统都会自动返回到调用这个函数的那个函数的对应位置。
这也可以叫做系统维护的回溯。是在代码里看不出来的。
如果做恢复现场的操作，就要自己手动去维护每次回溯需要恢复哪些额外的状态。
2.2 判断连通块是否为矩形：
来源：P1331 海战
bool pan(int i,int j){ //判断拐角的函数 int c=0; if(g[i][j]=='#')c++; if(g[i+1][j]=='#')c++; if(g[i][j+1]=='#')c++; if(g[i+1][j+1]=='#')c++; if(c==3)return 0; return 1; } int main() { qfor(i,n) //先判断图里是否为“ 标准 ”的实心矩形，当我们完成这一步之后图一定是合格的了，直接常规求连通块的板子就行了 qfor(j,m)if(i<n&&j<m&&pan(i,j)==0) { printf("Bad placement."); return 0; } } 2.2 关于DFS的搜索顺序
1.例：acwing 1116.马走日
这道题唯一要回溯的只有对结点的标记 st[ ] 数组
回溯方式有以下几种
#include <cstring> #include <iostream> #include <algorithm> #define debug(a,b) cout<<"#a = "<<a<<"#b = "<<b<<endl; using namespace std; const int N = 10; int n, m; bool st[N][N]; int ans; int dx[8] = {-2, -1, 1, 2, 2, 1, -1, -2}; int dy[8] = {1, 2, 2, 1, -1, -2, -2, -1}; void dfs(int x, int y, int cnt) { if (cnt == n * m) { ans ++ ; return; } st[x][y] = true; //在这里标记1 for (int i = 0; i < 8; i ++ ) { int a = x + dx[i], b = y + dy[i]; if (a < 0 || a >= n || b < 0 || b >= m) continue; if (st[a][b]) continue; dfs(a, b, cnt + 1); } st[x][y] = false; //在这里标记0 } int main() { int T; scanf("%d", &T); while (T -- ) { int x, y; scanf("%d%d%d%d", &n, &m, &x, &y); memset(st, 0, sizeof st); ans = 0; dfs(x, y, 1); printf("%d\n", ans); } return 0; } 或者这一种：
#include <cstring> #include <iostream> #include <algorithm> #define debug(a,b) cout<<"#a = "<<a<<"#b = "<<b<<endl; using namespace std; const int N = 10; int n, m; bool st[N][N]; int ans; int dx[8] = {-2, -1, 1, 2, 2, 1, -1, -2}; int dy[8] = {1, 2, 2, 1, -1, -2, -2, -1}; void dfs(int x, int y, int cnt) { if (cnt == n * m) { ans ++ ; return; } for (int i = 0; i < 8; i ++ ) { int a = x + dx[i], b = y + dy[i]; if (a < 0 || a >= n || b < 0 || b >= m) continue; if (st[a][b]) continue; st[a][b] = true; //在拓展递归的时候标记1 dfs(a, b, cnt + 1); st[a][b] = false; //在结束拓展递归的时候标记0回溯 } } int main() { int T; scanf("%d", &T); while (T -- ) { int x, y; scanf("%d%d%d%d", &n, &m, &x, &y); memset(st, 0, sizeof st); ans = 0; st[x][y] = true; //由于这样照顾不到起点了，所以预处理 dfs(x, y, 1); st[x][y] = false; //同样是预处理起点 printf("%d\n", ans); } return 0; } 这两种没什么区别，
至于像下面这样打了好几次标记，纯纯浪费时间，没必要。
voiddfs(int x,int y,int cnt){ st[x][y]=true;if(cnt == n * m){ ans ++;return;}for(int i =0; i <8; i ++){int a = x + dx[i], b = y + dy[i];if(a <0|| a >= n || b <0|| b >= m)continue;if(st[a][b])continue; st[a][b]=true;dfs(a, b, cnt +1); st[a][b]=false;}}2.例：acwing 1117.单词接龙
对于处理字符串有点提示帮助
#include <cstring> #include <iostream> #include <algorithm> using namespace std; const int N = 21; int n; string word[N]; int g[N][N]; int used[N]; //使用次数，需要小于2 int ans; void dfs(string dragon, int last) //last表示当前接的最后一个单词的编号是多少 { ans = max((int)dragon.size(), ans); //因为max里的参数需要是同种类型，我们给强转成int used[last] ++ ; for (int i = 0; i < n; i ++ ) if (g[last][i] && used[i] < 2) dfs(dragon + word[i].substr(g[last][i]), ); //这里，g[last][i]存的是last 和 i最小重合的部分，重合部分是不能加的，要从重合部分往后开始加，这里substr(g[last][i])指的就是从这个从这个字母往后的部分，第二维省略表示正无穷长度。 used[last] -- ; } int main() { cin >> n; for (int i = 0; i < n; i ++ ) cin >> word[i]; char start; cin >> start; for (int i = 0; i < n; i ++ ) for (int j = 0; j < n; j ++ ) { //很巧妙的预处理，g[i][j]存储的是他们之间最短的可相连长度（最小重合部分） string a = word[i], b = word[j]; //学学subsrt( )函数，处理字符串挺有用 for (int k = 1; k < min(a.size(), b.size()); k ++ ) if (a.substr(a.size() - k, k) == b.substr(0, k)) { g[i][j] = k; break; } } for (int i = 0; i < n; i ++ ) if (word[i][0] == start) dfs(word[i], i); //传一下编号 cout << ans << endl; return 0; } 2.3 八皇后
来源：P1219 [USACO1.5] 八皇后 Checker Challenge
经典的DFS回溯，没别的意思，我就单纯的想放一下。
设置四个数组，分别标记行， 列， / 对角线，\ 对角线 四个位置上是否存在。
很简洁的代码：
#include<bits/stdc++.h> using namespace std; #define TLE ios::sync_with_stdio(0),cin.tie(0) #define endl "\n" #define sfor(i,n) for(int i=1; i<=n; i++) int a[20],b[20],c[20],d[20]; int sum,n; void dfs(int i) { if(i>n){ if(sum<=2){ for(int k=1;k<=n;k++)cout<<a[k]<<" "; cout<<endl; } sum++; return; } else{ sfor(j,n){ if(b[j]==0 && c[i+j]==0 && d[i-j+n]==0){ a[i]=j; b[j]=1; c[i+j]=1; d[i-j+n]=1; dfs(i+1); a[i]=0; b[j]=0; c[i+j]=0; d[i-j+n]=0; } } } } int main() { cin>>n; dfs(1); cout<<sum; return 0; } 2.4 图的搜索顺序—换行处理
acwing 843.n皇后问题
第一种是着重在剪枝
//在此处，为了模拟坐标轴，使用u替换y，使用i替换x #include<iostream> using namespace std; const int N=20;//此处x轴和y轴的长度为10，开20是大了，但是对角线长度约1.414*10（根号2），所以数组开大有好处 int n;//此处存储输入的行数&列数, char q[N][N];//构建棋盘，大一些没坏处，注意类型需要为char（一开始无语写了个int） bool col[N],dg[N],udg[N];//col是Column（列）的缩写，dg是diagonal（对角）的缩写，（反对角线前面的u想不出了） //设udg的方程为y=x+b则b=y-x，替换后b=u-i，防止出现负数，则加上偏移量n，则有b=u+n-i（其实b=n+i-u也可，目的是一个对角线能单独映射） //设dg的方程为y=-x+b,b=y+x,替换后b=i+u,perfect void dfs(int u){//已经操作了u行 if(u==n){//好家伙，已经操作完u行了，一个输出了 for(int i=0;i<n;i++){ cout<<q[i]<<endl; } cout<<endl; /*这种写法也可，但是如果上面的看不懂建议补习C语言基础 for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ cout<<q[i][j]; } cout<<endl; } cout<<endl; */ return; } for(int i=0;i<n;i++){//到这一步说明还没有dfs搜索完 if(!col[i] and !dg[i+u] and !udg[u+n-i]){//这个点在各种映射下都是合法的 q[u][i]='Q'; col[i]=dg[i+u]=udg[u+n-i]=true;//这些点用掉啦 dfs(u+1);//继续往下一层探 col[i]=dg[i+u]=udg[u+n-i]=false;//出来后这些点恢复原状 q[u][i]='.'; } } } int main(){ cin>>n;//输入行数 for(int i=0;i<n;i++){//搭建一个“船新”的棋盘 for(int j=0;j<n;j++){ q[i][j]='.'; } } dfs(0);//0代表目前已经操作了0行，并且需要对第1行进行操作（在数组中映射为0行） return 0; } 第二种搜索方式：遍历每一行，当到结尾的时候到下一行，每次判断这个点是否满足，满足就放一个Q，最后遍历到最后一行的时候如果刚好放了n个Q，说明完成了，输出。
第二种的巧妙在于换行的处理：
if (s > n) return; if (y == n) y = 0, x ++ ; code
#include <iostream> using namespace std; const int N = 10; int n; bool row[N], col[N], dg[N * 2], udg[N * 2]; char g[N][N]; void dfs(int x, int y, int s) { if (s > n) return; if (y == n) y = 0, x ++ ; if (x == n){ if (s == n){ for (int i = 0; i < n; i ++ ) puts(g[i]); puts(""); } return; } g[x][y] = '.'; dfs(x, y + 1, s); if (!row[x] && !col[y] && !dg[x + y] && !udg[x - y + n]) { row[x] = col[y] = dg[x + y] = udg[x - y + n] = true; g[x][y] = 'Q'; dfs(x, y + 1, s + 1); g[x][y] = '.'; row[x] = col[y] = dg[x + y] = udg[x - y + n] = false; } } int main() { cin >> n; dfs(0, 0, 0); return 0; } 2.5 DFS搜索矩阵图巧妙换行方式
来源：P1123 取数游戏
这道题题不难，但是关于深搜有了一些很不错的新东西。
因为我们搜索的是一张图，所以在搜索的时候要面面临：
- 一行搜完了如何换到下一行的问题
- 如何判断搜索结束的条件
- 如何回溯和剪枝
- 在搜索的时候起点也是不唯一的，如何解决这个问题
首先看看我的错误示范：
我企图在solve函数中遍历图上的每一个点当做起点的dfs，试图这样来解决起点的问题
我企图再dfs函数里也遍历图上的点来通过双重循环实现行的转换
我企图用st[ i ]存储三种数字来表示选中的位置，作为邻居不能被选的位置，和我们还没标记的位置。
我企图用tank桶数组来装不能选的数字有哪些。
但是实际上我的做法是漏洞百出的。
- 首先，有一些点在上一次被当做邻居标记了，这一次搜索重复标记了，但是在这一次的回溯中我直接全部赋值为0，相当于这些上一点的邻居的标记被消掉了，这是错误的。所以应该改进为记录被当做邻居的次数（ ++ ），回溯的时候只需要减一（ – ），就不会出错了。
- 我的代码 太烂了 我已经找不完我的毛病了，太多啦！直接跳过看正解的代码吧！！！呜呜呜QAQ
int n, m, t; int g[N][N], st[N][N]; int ans, ant; int tank[N]; int turn_x[8]={0,0,1,-1,1,-1,1,-1}; int turn_y[8]={1,-1,0,0,1,-1,-1,1}; void dfs(int x,int y) { st[x][y] = 2; for(int o=0;o<8;o++){ int xx =x+turn_x[o];int yy=y+turn_y[o]; if(xx>=1 && yy>=1 && xx<=n && yy<=m && st[xx][yy] != 2){st[xx][yy] = 1;tank[g[xx][yy]] = 1;} } ant += g[x][y]; st[x][y] = 2; ans = max(ans,ant); for(int i=x; i<=n; i++) for(int j=1; i<=m; j++){ if(st[i][j] > 0)continue; if(tank[g[i][j]] > 0)continue; dfs(i,j); } } void solve() { cin>>n>>m; sfor(i,n) sfor(j,m)cin>>g[i][j]; sfor(i,n) sfor(j,m){ memset(st,0,sizeof(st)); memset(tank,0,sizeof(tank)); ans = 0;ant = 0; dfs(i,j); } cout<<ans<<endl; } ！！！大佬的正解来喽！！！
- 还有就是一定要注意当行数大于 n 的时候已经搜完了，所以要return;
- 如果没选调用的是：DFS(i,j+1)如果选了的话调用的是：DFS(i,j+2)这里是我们因为有了换行，所以每次让 j + 1 就可以了，如果选了一个数因为要把其周围一圈的数都变成不可选中转态，所以可以直接多跳一行了。
大佬并没有用双层循环遍历，而是直接在solve函数里调用dfs( 1 , 1 )，然后每次调用一次选的dfs，调用一次不选的dfs。这样就很巧妙的实现了动态的搜索！还有就是大佬的换行方式是：
void DFS(int i,int j,int now){//i为行，j为列，now为现值 if(j>m){//列超出，行+1，列归1 i++; j=1; } if(i>n){//行超出，更新ans，结束 if(now>ans)ans=now; return; } int k; if(can[i][j]==0){//选 for(k=1;k<9;k++)can[i+dx[k]][j+dy[k]]++;/*此次不能用bool存储，可能有多重状态*/ DFS(i,j+2,now+a[i][j]); for(k=1;k<9;k++)can[i+dx[k]][j+dy[k]]--; } DFS(i,j+1,now);//不选 } #include<bits/stdc++.h>//万能头文件 using namespace std; const int d[8][2]={1,0,-1,0,0,1,0,-1,1,1,-1,1,1,-1,-1,-1};//方向数组用来控制搜索时的方向 int t,n,m,s[8][8],mark[8][8],ans,mx; void dfs(int x,int y){//搜索函数，表示搜索点(x,y) if(y==m+1){//当y到边界时，搜索下一行 dfs(x+1,1); return; } if(x==n+1){//当x到边界时，搜索结束，刷新最大值 mx=max(ans,mx); return; } dfs(x,y+1);// 不取此数的情况 if(mark[x][y]==0){ //取此数的情况（需保证此数周围没有取其他数，即mark[i][j]==0） ans+=s[x][y]; for(int fx=0;fx<8;++fx){ //标记周围的数 ++mark[x+d[fx][0]][y+d[fx][1]]; } dfs(x,y+2); for(int fx=0;fx<8;++fx){ //回溯 --mark[x+d[fx][0]][y+d[fx][1]]; } ans-=s[x][y]; } } int main(){ cin>>t; while(t--){ memset(s,0,sizeof(s)); memset(mark,0,sizeof(mark));//在做每个数据前都要初始化数组 cin>>n>>m; for(int i=1;i<=n;++i){ for(int j=1;j<=m;++j){ cin>>s[i][j]; } } mx=0; dfs(1,1);//从点(1,1)开始搜索 printf("%d\n",mx);//输出答案 } return 0; } 3. DFS剪枝搜索
剪枝某种程度上说可以看成一种提前回溯
记忆化搜索（DP）
最优性剪枝
可行性剪枝
排除等效冗余
优化搜索顺序(大部分情况下，我们应该优先搜索分支较少的节点)
Acwing 165.小猫爬山
- 先思考如何正确的搜到所有情况：暴搜枚举，枚举当前这只小猫应该放在那辆车上，或者开一俩新车承载小猫。
- 然后开始考虑搜索顺序与剪枝：关于 优化搜索顺序 ： 可以想到优先放重的猫更好。
这里推荐一个思路描述很清晰的大佬题解：https://www.acwing.com/solution/content/32118/
Acwing 166.数独
- 先思考如何正确的搜到所有情况：每次随机选一个代填空的格子，然后枚举填入可选的数字
- 考虑搜索顺序与剪枝：关于 优化搜索顺序 ： 每次去选择备选方案最少的格子（分支最少的格子）关于 可行性剪枝 ： 每次选择一个格子，不能与所在的行，所在的列，所在的九宫格有重复。关于 位运算有优化 ：这道题用到了位运算优化：可以用一个九位的二进制数字代表一个状态，一次判断可行性
- 分别用二进制代表行的状态，列的状态，九宫格的状态，然后求交集【即必须三种情况都满足为1（ture）才行，所以选择使用按位与】
- 交集（按位与）得到一个01二进制串，其中“1”的部分是可以选择的，每次只需要循环< 1 > 个数次即可，不用都循环九次。
- 在枚举可选择数字方案的时候，使用< lowbit > 求最后一位 < 1 >在哪，
code：
#include <cstring> #include <iostream> #include <algorithm> using namespace std; const int N = 9, M = 1 << N; //ones表示0-2^9里每个数有多少个1，map快速地找出这行哪一列可以填，比如map[(10)2] = 1就知道第二列可以填1 int ones[M], map[M]; //分别表示行，列，大方格子有哪些数字没有填 int row[N], col[N], cell[3][3]; char str[100]; void init() //预处理 { for (int i = 0; i < N; i ++ ) row[i] = col[i] = (1 << N) - 1; for (int i = 0; i < 3; i ++ ) for (int j = 0; j < 3; j ++ ) cell[i][j] = (1 << N) - 1; } //is_set = true则在x, y填上t, 否则则把x,y处的数字删掉, t 是0-8 void draw(int x, int y, int t, bool is_set) { if (is_set) str[x * N + y] = '1' + t;//t 是0-8 else str[x * N + y] = '.'; int v = 1 << t; if (!is_set) v = -v; //如果某位没被放，则它的二进制位应该是1， 所以应该减去v //如果放了，它的二进制应该是0，则经过上面的取反，负负得正，-v实际上就是把二进制0变为1 row[x] -= v; col[y] -= v; cell[x / 3][y / 3] -= v; } int lowbit(int x) { return x & -x; } //x行y列可以填哪个数字, 最后得到2^i + 2^j..+..，这些i, j就是可以填的数字，最后通过map[2^i]来得到这个数字 int get(int x, int y) { return row[x] & col[y] & cell[x / 3][y / 3]; } bool dfs(int cnt) { //填完所有数字，则返回 if (!cnt) return true; //最多可以填多少个数字 int minv = 10; int x, y; for (int i = 0; i < N; i ++ ) for (int j = 0; j < N; j ++ ) if (str[i * N + j] == '.') { //可以填的数字状态，如010001，是1则表示可以填 int state = get(i, j); //选一个1的个数最少的，这样的分支数量最少 if (ones[state] < minv) { minv = ones[state]; x = i, y = j; } } int state = get(x, y); //依次做lowbit操作，选择每个分支 for (int i = state; i; i -= lowbit(i)) { //这个t就是要填充的数字 int t = map[lowbit(i)]; draw(x, y, t, true);//填这个数字 if (dfs(cnt - 1)) return true;//这次填充成功，则返回 draw(x, y, t, false);//失败则回溯 } return false; } int main() { //打表，快速地知道可以哪一个数字 for (int i = 0; i < N; i ++ ) map[1 << i] = i; //ones记录每个状态有多少个1，用于选择分支少的开始搜索, 其中M = 1 << N for (int i = 0; i < 1 << N; i ++ ) for (int j = 0; j < N; j ++ ) ones[i] += i >> j & 1; //每个数二进制有多少个1 while (cin >> str, str[0] != 'e') { init(); //cnt表示还剩多少个数字没有填 int cnt = 0; for (int i = 0, k = 0; i < N; i ++ ) for (int j = 0; j < N; j ++, k ++ ) if (str[k] != '.') { int t = str[k] - '1'; draw(i, j, t, true); } else cnt ++ ; dfs(cnt); puts(str); } return 0; } 【优秀题解（有图文）：https://www.acwing.com/solution/content/56364/】
【舞蹈链解法题解：https://www.acwing.com/solution/content/3843/】
AcWing 167. 木棒
- 先思考如何正确的搜到所有情况：木棒由木棍拼接而成，先枚从小打到枚举木棒的长度，对于固定的木棒长度，然后枚举木棍去拼接，如果可以恰好拼好那就合法。
- 再考虑搜索顺序与剪枝：关于 优化搜索顺序 ： 先枚举较长的木棍，从大到小枚举关于 排除等效冗余 ：
- 比如<1,3,2>和<1,2,3>和<3,2,1>这样的枚举结果重复了，所以不应该按照排列数的顺序去枚举【考虑顺序】，而应该按照组合数来枚举【不考虑顺序】
- 如果当前木棍加到当前木棒中失败了，那么直接略过所有等长木棍【因为等长，所以也一定会失败】
- 如果有一根木棍放在某木棒开头失败了（dfs找不到解），那么一定失败
- 如果有一根木棍放在某木棒结尾失败了（dfs找不到解），那么一定失败3.和4.的反证法证明：假如一根木棍放在某木棒开头（结尾）dfs找不到解，那么只能是被安排到另一根木棒中间，原本的位置被其他木棍拼搭代替的情况最后有解。但是这两处等长，交换回去之后相当于存在这根木棍放在某木棒的开头（结尾）并且存在解，那么就矛盾了。
- 后一根不行，是表示找不到一组合法的题目要求的解，而不是表示放在当前大木中不合法。
假如一根小木放在当前大木中最后一个不行，那么可以判断它放在任何一根大木中都不行，不存在题目要求的可以把所有小木放在若干个大木中正好放满。
上面判断的证明：反证法：假如有一根小木放在当前大木x的最后一根不行，但是放在其他大木y的任意位置行，则大木y中该小木可以通过平移使得该小木置于最后一个位置，这样就存在方案使得该小木放在大木最后一个位置可行，与假设相悖，得证【借鉴题解：https://www.acwing.com/solution/content/36030/】
4.DFS洛谷题
4.1 利用二进制表示排列组合
来源：P6183 [USACO10MAR] The Rock Game S
1.exit(0);~ //在递归函数里用这条语句可以直接结束整个程序 //其实还有一种方法： if(b==1)return;//如果已经输出了就终止其他的dfs 2.int calc(){//将一个二进制数转化为十进制数 int ans=0; for(int i=1;i<=n;i++){ ans=ans*2+a[i];//常规操作 } return ans; } 3.类似于长度为n的数组，每个位置只有两种可能(如为'X' or 'Y')，其实可以看做一个二进制的数， 将这个二进制转化成十进制，这样不同位置组成不重复的排列组合就形成了不重复的十进制数。 //如：9(1001)代表 XYYX【设X为1， Y为0】 //妙啊！好女口阿！ 4.如何让一个数组的某一个元素在0和1之间快速转化： for(int i=1;i<=n;i++){ a[i]=!a[i];//一位差别 if(vis[calc()]){//走过了 a[i]=!a[i];//还原 }//在这个dfs里我们就成功的用十进制数来代替了一个YX组成的数组被判断 这里有一篇ZEEKLOG的大佬：辅玉
他提供了两个重要的思路解读：
4.1.1.难点
本题最大的难点在于如何判断奶牛到达的某种状态是否在之前出现过。实际上，既然每个洞只有两种状态，那么我们可以用二进制中的0、1与之分别对应。这样的话，n个洞的每一种状态就可以用一个独一无二的二进制数来表示。我们再建立一个标记数组visit [ ] 来记录每个二进制数（可以先将其转化为十进制数）是否被访问过。例如OOX表示二进制数001，转换成十进制数就是1。
4.1.2.核心思路
这是一道典型的搜索题，可以利用DFS来做。
设共有n个洞，当前是第step步，把所有洞的状态叫做整体状态。
除去初始时所有洞全空的状态，完成这个游戏一共需要2^n步。
- 判断当前是否是第2^n步。
- 若是，说明已经找到了可行解，停止搜索，直接退出程序；因为第2^n步也是所有洞全空，我们可以在最后直接打印出来
- 每到达一种整体状态，从第1个洞开始依次选取一个洞将其的状态取反，然后判断新的整体状态是否被访问过：若访问过，则将这个洞的状态复原，然后继续选择下一个洞；
- 若未访问过，将此整体状态标记为已访问过（visit [ ]=1)，然后将这个整体状态存入数组记录下来，然后进行下一步搜索（DFS（step+1))
- 回溯时将刚才改动的洞的状态复原,将此整体状态标记为未访问过（visit [ ]=0）
4.1.3.ps：刚开始要把第0步的全空状态标记为已访问过！！！
visit[0]=1;ac code：
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; int n; int a[20];//记O为0，X为1 int vis[1<<20+10]={1};//vis[0]提前标记，不然n=2,3会错 int ans[1<<20+10][20],tot=0; void output(){//输出函数 for(int i=1;i<=1<<n;i++){ for(int j=1;j<=n;j++){ cout<<(ans[i][j]?'X':'O'); } cout<<endl; } } int calc(){//将一个二进制数转化为十进制数 int ans=0; for(int i=1;i<=n;i++){ ans=ans*2+a[i];//常规操作 } return ans; } void dfs(int pos){ if(pos==(1<<n)){//因为ans初始化时OOOOO...OO，所以最后留一组输出即可 output();//输出 exit(0);//SPJ，找到一组即可 } for(int i=1;i<=n;i++){ a[i]=!a[i];//一位差别 if(vis[calc()]){//走过了 a[i]=!a[i];//还原 continue;//再见 } vis[calc()]=true;//记录，走过了 for(int j=1;j<=n;j++){ ans[pos][j]=a[j];//存储答案 } dfs(pos+1);//继续搜索下一个 vis[calc()]=false;//回溯 a[i]=!a[i];//注意：不能颠倒，被坑了一次 } } int main(){ cin>>n; for(int i=1;i<=n;i++) cout<<'O';//输出 cout<<endl; vis[0]=true;//OOO.OOO不可再走 dfs(1); //从1开始搜索 return 0; } 4.2 DFS优化——记忆化搜索
来源：P1464 Function
本体原本只是简单的递归，但是由于机制一些数据会重复递归多次导致时间爆炸，所以我们采用了记忆化搜索
- 由于超过20会直接返回，所以我们只需要给前三维 25 数组的点记忆化标记即可
- 由于数组的下标不能为负数，但是题目中给的值又可能为负数，那样会报错，所以我们先让判断如果小于0直接返回的判断写在前面
- 具体的记忆化搜索可以是如果该点的出过答案直接返回答案。
const int N=2e5+10; int n,m,k; int st[25][25][25]; int vis[25][25][25]; int w(int a,int b,int c){ if(a <= 0 || b <= 0 || c <= 0)return 1; if(a > 20 || b > 20 || c > 20)return w(20, 20, 20); if(vis[a][b][c])return st[a][b][c]; if(a<b && b<c) st[a][b][c]=w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c); else st[a][b][c]=w(a-1,b,c)+w(a-1,b-1,c)+w(a-1,b,c-1)-w(a-1,b-1,c-1); vis[a][b][c]=1; return st[a][b][c]; } signed main() { TLE; memset(st,-1,sizeof(st)); while( scanf("%ld%ld%ld",&n,&m,&k)){ if(n == -1 && m == -1 && k == -1)return 0; else cout<<"w("<<n<<", "<<m<<", "<<k<<')'<<" = "<<w(n,m,k)<<endl; } return 0; } 4.3 DFS递归优化
来源;P9011 [USACO23JAN] Air Cownditioning II B
这原本是一道和 P1460 [USACO2.1]健康的荷斯坦奶牛 Healthy Holsteins 一样的经典递归题，不过题解给出的解法有一些小差别。
原本的奶牛的 check 函数是用数组存下所选的饲料编号，然后在函数里把这些饲料的维他命都加起来判断是否符合奶牛的所需
用这道题的一个题解的思路加以改进就是：先初始化一个数组 tool（初始化为牛所需要的维他命），然后每次调用dfs的时候给 tool 数组的维他命减去所选的饲料提供的维他命，回溯的时候加回来。这个时候 check 函数就只需要for循环判断 tool 数组是否都小于 0 即可。
check函数从两层循环变成了只需要一层循环【虽然也算优化了，但是影响几乎可以忽略不计】
int n,m,k,ans=1e9,cw[105],s[25],t[25],c[25],a[25],b[25],p[25],v[25]; int st[105]; int val; bool pan() { for(int i=1;i<=k;i++) { if(cw[i]>0) return 0; } return 1; } void dfs(int pos){ if(pos > m)return; if(ans <= val)return; st[pos] = true; if(pan()){ ans=min(ans,val); // cout<<"ans："<<ans<<" pos:"<<pos<<endl; return; } for(int r=pos; r<=m; r++) if(!st[r]) { st[r] = true; for(int i=a[r];i<=b[r];i++)cw[i]-=p[r]; val += v[r]; dfs(r); st[r] = false; val -= v[r]; for(int i=a[r];i<=b[r];i++)cw[i]+=p[r]; } } int main() { cin>>n>>m; qfor(i,n){ cin>>s[i]>>t[i]>>c[i]; k=max(k,t[i]); for(int j=s[i];j<=t[i];j++) cw[j]+=c[i]; } qfor(i,m)cin>>a[i]>>b[i]>>p[i]>>v[i]; dfs(0); cout<<ans<<endl; return 0; } 4.5 DFS标记路径得到割点
来源：P8604 [蓝桥杯 2013 国 C] 危险系数
本题题解有一个很巧妙的写法，就是通过dfs给每一条走到终点的路径上的节点打上标记，到最后如果节点的被走过次数等于能达到终点的路径总数，那么这个点就一定是每条路径都必须经过的点。
ps：这里还有一个，就是关于用二维数组和二维vector存储邻接矩阵的一些小区别。
//这是用二维数组的邻接矩阵的用法 #include<bits/stdc++.h> #define LL long long #define made return #define in 0 #define China ; using namespace std; LL n,m,u,v,ans,cnt[1010],sum; bool bj[1010],a[1010][1010]; void dfs(LL now) if(now==v){//如果走到终点了， sum++;//路径总数加一。 for(int i=1;i<=n;i++) if(bj[i]==1)cnt[i]++;//每个被走过的点，被走总次数加一 } else{ for(int i=1;i<=n;i++) if(a[now][i]==1&&bj[i]==0){//如果两点连通且下一步要走到的点未被走过， bj[i]=1;//标记。 dfs(i); bj[i]=0;//回溯一步。 } } } int main(){ scanf("%lld%lld",&n,&m); while(m--){ scanf("%lld%lld",&u,&v); a[u][v]=a[v][u]=1;//输入邻接矩阵。因为是无向的，所以u到v和v到u都要设为1。 } scanf("%lld%lld",&u,&v); dfs(u); if(sum>0){//dfs求解 for(int i=1;i<=n;i++) if(cnt[i]==sum)ans++;//如果这个点被走过的总次数与路径总数相等，那么删去这个点起点与终点间一定不连通。 printf("%lld",ans-1);//因为起点也被算在内，所以总危险系数要减去起点的1。 } else printf("-1");//如果询问的两点无路径连通则输出'-1'。 } //这是用vector二维数组写的，这种写法会和普通的二维数组有一些区别 #include<bits/stdc++.h> using namespace std; const int N=1005; vector<int>a[N];//a[i]表示所有与i点相连通的点 int n,m,x,y,b,ans[N],M,ans_end;//见上描述 bool t[N]; void dfs(int dq){ if(dq==y){ b++; for(int i=1;i<=M;i++)ans[i]+=t[i]?1:0;//区别之一，这里其实没啥区别，只是if的另一种写法，或许看起来会更酷吧 return; } t[dq]=true; for(auto to:a[dq]){//区别之一，这里的遍历并不是直接暴力的从头到n找一遍，看看哪些存在。而是直接用auto if(t[to])continue; dfs(to); } t[dq]=false; } int main(){ scanf("%d%d",&n,&m); for(int i=1,xa,ya;i<=m;i++){ scanf("%d%d",&xa,&ya); a[xa].push_back(ya);//存入 a[ya].push_back(xa); M=max(max(M,xa),ya);//区别之一，这里循环遍历并不是到n，而是到存入的最大节点（不知道为什么这么写，但是改成n也是对的） } scanf("%d%d",&x,&y); dfs(x); for(int i=1;i<=M;i++)if(ans[i]==b)ans_end++; printf("%d",ans_end-1);//见上描述 return 0; } 5. BFS简介
BFS：搜一棵树，一层一层往下扩展
数据结构：用的是队列 queue ； 空间：O( 2的h次方 )
BFS特点：1.基于迭代，所以不会爆栈，有时候dfs和bfs相比，bfs会更优
6. BFS中的Flood Fill和最短路模型
6.1【洪水填充法】
————————————————————————————————————————
可以在线性时间复杂度内，找到某个点所在的连通块。
既可以用宽搜也可以用深搜，但是深搜可能会容易爆栈，所以尽量用宽搜写。
————————————————————————————————————————
- 知识点1.y总用到：
#define x first #define y second - 这样可以更快的调用pair数组，也有人写成：
#define _1 first #define _2 second - 知识点2：y总遍历八联通的时候用的是暴力判九宫格，确实很暴力，也是一种写法
for (int i = t.x - 1; i <= t.x + 1; i ++ ) for (int j = t.y - 1; j <= t.y + 1; j ++ ) { if (i == t.x && j == t.y) continue; //避免中间这个格子，只需要判断周围八个格子 if (i < 0 || i >= n || j < 0 || j >= m) continue; //越界 if (g[i][j] == '.' || st[i][j]) continue; //是否符合条件，并且未被走过 //当我们走完了之后就是合法的，然后入队列 q[ ++ tt] = {i, j}; st[i][j] = true; } 当然，用方向向量写也很经典
//向北，x-1，y不变；dx[0]=-1,dy[0]=0;//向南，x+1，y不变；dx[0]=1,dy[0]=0;//向东，x不变，y+1；dx[0]=0,dy[0]=1;//向西，x不变，y-1；dx[0]=0,dy[0]=-1;例题：AcWing 1097. 池塘计数
#include <cstring> #include <iostream> #include <algorithm> #define x first #define y second using namespace std; typedef pair<int, int> PII; const int N = 1010, M = N * N; int n, m; char g[N][N]; PII q[M]; bool st[N][N]; void bfs(int sx, int sy) { int hh = 0, tt = 0; q[0] = {sx, sy}; st[sx][sy] = true; while (hh <= tt) { PII t = q[hh ++ ]; for (int i = t.x - 1; i <= t.x + 1; i ++ ) for (int j = t.y - 1; j <= t.y + 1; j ++ ) { if (i == t.x && j == t.y) continue; if (i < 0 || i >= n || j < 0 || j >= m) continue; if (g[i][j] == '.' || st[i][j]) continue; q[ ++ tt] = {i, j}; st[i][j] = true; } } } int main() { scanf("%d%d", &n, &m); for (int i = 0; i < n; i ++ ) scanf("%s", g[i]); int cnt = 0; for (int i = 0; i < n; i ++ ) for (int j = 0; j < m; j ++ ) if (g[i][j] == 'W' && !st[i][j]) { bfs(i, j); cnt ++ ; } printf("%d\n", cnt); return 0; } ————————————————————————————————————————
- 知识点4：这有一个写法，巧妙的用二进制存
来源：acwing1098. 城堡问题
这道题的上下左右墙分别对应数字1,2,4,8，每个位置输入的值是周围墙的数字之和。
虽然只是一道简单的求连通块的最大面积，但是图给的很不寻常。
这里用到了一个不错的写法，就是用二进制来存这个数字之和，**通过每一位是0还是1来判断1,2,4,8，是否加进来了。**就很灵性。
#include <cstring> #include <iostream> #include <algorithm> #define x first #define y second using namespace std; typedef pair<int, int> PII; const int N = 55, M = N * N; int n, m; int g[N][N]; PII q[M]; bool st[N][N]; int bfs(int sx, int sy) { int dx[4] = {0, -1, 0, 1}, dy[4] = {-1, 0, 1, 0}; //因为x轴是向下方向的，y轴是向右方向的，所以这里对应的分别是西，北，东，南， int hh = 0, tt = 0; int area = 0;//记录面积 q[0] = {sx, sy}; st[sx][sy] = true; while (hh <= tt) { PII t = q[hh ++ ]; area ++ ; for (int i = 0; i < 4; i ++ ) { int a = t.x + dx[i], b = t.y + dy[i]; if (a < 0 || a >= n || b < 0 || b >= m) continue; if (st[a][b]) continue; if (g[t.x][t.y] >> i & 1) continue; //这是一个很骚的操作，因为1,2,4,8,在二进制里刚好都是不同位置上是1，其余都是0，所以每次右移一位看是1还是0就知道这个方向是否有墙了。这也是这道题很骚的地方，二进制判断。 q[ ++ tt] = {a, b}; st[a][b] = true; } } return area; } int main() { cin >> n >> m; for (int i = 0; i < n; i ++ ) for (int j = 0; j < m; j ++ ) cin >> g[i][j]; int cnt = 0, area = 0; for (int i = 0; i < n; i ++ ) for (int j = 0; j < m; j ++ ) if (!st[i][j]) { area = max(area, bfs(i, j)); cnt ++ ; } cout << cnt << endl; cout << area << endl; return 0; } ————————————————————————————————————————
- 知识点5：没啥要说的，一个变种的例题
来源：AcWing 1106. 山峰和山谷
#include <cstring> #include <iostream> #include <algorithm> #define x first #define y second using namespace std; typedef pair<int, int> PII; const int N = 1010, M = N * N; int n; int h[N][N]; PII q[M]; bool st[N][N]; void bfs(int sx, int sy, bool& has_higher, bool& has_lower) { int hh = 0, tt = 0; q[0] = {sx, sy}; st[sx][sy] = true; while (hh <= tt) { PII t = q[hh ++ ]; for (int i = t.x - 1; i <= t.x + 1; i ++ ) for (int j = t.y - 1; j <= t.y + 1; j ++ ) { if (i == t.x && j == t.y) continue; if (i < 0 || i >= n || j < 0 || j >= n) continue; if (h[i][j] != h[t.x][t.y]) // 山脉的边界 { if (h[i][j] > h[t.x][t.y]) has_higher = true; else has_lower = true; } else if (!st[i][j]) { q[ ++ tt] = {i, j}; st[i][j] = true; } } } } int main() { scanf("%d", &n); for (int i = 0; i < n; i ++ ) for (int j = 0; j < n; j ++ ) scanf("%d", &h[i][j]); int peak = 0, valley = 0; for (int i = 0; i < n; i ++ ) for (int j = 0; j < n; j ++ ) if (!st[i][j]) { bool has_higher = false, has_lower = false; bfs(i, j, has_higher, has_loweBFS呆r); if (!has_higher) peak ++ ; if (!has_lower) valley ++ ; } printf("%d %d\n", peak, valley); return 0; } 6.1.1 BFS涂色
来源：P1162 填涂颜色
思路：直接从墙边缘开始找0的连通块，这些一定是不封闭的0，其余的都是被1封闭包围的
6.2. 最短路问题
【具有最短路性质，第一次搜到的点一定是距离最近的点，因为他是一层一层的搜】
当边权都为1的时候最短路问题可以拿BFS写
【这思路是acwing中y总传授的，让我茅塞顿开】
这里讲了一个证明BFS求得最短路的证明：
首先，BFS中的队列存在两个性质：
- 1.两段性：队头假如是与目标距离为 x ，那么从队头弹出的元素拓展进队尾的点只能是距离为 x+1，【因为边权都是1】，在队里中所有的距离为 x 的点都被弹出之前，队列的另一段只能是 x+1，不可能出现别的数字。如：[ x x x x+1 x+1 x+1 x+1 ]
- 2.单调性：从两段性我们发现BFS代码中的队列是由至多两段组成的（可能只有x，没有x+1，就是一段了），所以元素是一定满足非严格升序的，即存在单调性。
通过以上两种性质，我们可以发现这很像所有边权都为1的堆优化版dijstra，堆优化每次弹出队列的都是当前队列中最小的，在bfs的队列中由于单调性也可以保证这一点。
并且由于边权都是1，所以每次更新拓展进优先队列的点也一定是 x+1，这里的思路和bfs是相像的，所以也能间接证明BFS求最短路的能力。
来源：acwing 844.走迷宫
#include<bits/stdc++.h> using namespace std; const int N=110; //n,m的数据范围均为100 int g[N][N],d[N][N],n,m; //g[N][N]用来存储迷宫( 图 ) queue <pair<int,int>> q; //d[x][y]用来存储(x,y)这一点到坐标原点的距离 //q队列用来存储宽度优先搜素到的路径也就是走迷宫经过哪些点 int bfs() { memset(d,-1,sizeof d); //将d数组所有元素初始化为-1 d[0][0]=0; //位于原点时到原点的距离为0 q.push({0,0}); //将原点入队 int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1}; //定义方向向量一共四个方向 while(q.size()) //当队列非空时执行循环 { auto t=q.front(); q.pop(); // ！！！插入一个位置的同时会弹出一个位置保证循环可以正常终止 for(int i=0;i<4;i++) //x,y都要四个方向,遍历四个方向 { int x=t.first+dx[i],y=t.second+dy[i]; //四个方向对应x,y坐标 if(x>=0 && x<n && y<m && y>=0 && g[x][y]==0 && d[x][y]==-1 ) { d[x][y]=d[t.first][t.second]+1; //走到下一个点的同时距离加1 q.push({x,y}); //将该点入队 } } } return d[n-1][m-1]; //reruen递归到右下角时的结果 } int main() { scanf("%d%d",&n,&m); //输入迷宫的尺寸大小 for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { scanf("%d",&g[i][j]); //输入迷宫 } } cout<<bfs()<<endl; //输出宽度优先搜索结果 return 0; } 是在bfs求最短路的基础上多了一个要输出路径，比如用递归实现路径输出
来源：AcWing 1076. 迷宫问题
#include <cstring> #include <iostream> #include <algorithm> #define x first #define y second using namespace std; typedef pair<int, int> PII; const int N = 1010, M = N * N; int n; int g[N][N]; PII q[M]; PII pre[N][N]; //看一个数是否被遍历过 void bfs(int sx, int sy) { int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}; int hh = 0, tt = 0; q[0] = {sx, sy}; memset(pre, -1, sizeof pre);//初始成 -1 表示没搜过。 pre[sx][sy] = {0, 0};//这里只是标记一下起点，不为 -1 就代表走过了，是不是0都可以。 while (hh <= tt) { PII t = q[hh ++ ]; for (int i = 0; i < 4; i ++ ) { int a = t.x + dx[i], b = t.y + dy[i]; if (a < 0 || a >= n || b < 0 || b >= n) continue; if (g[a][b]) continue; if (pre[a][b].x != -1) continue; //如果之前已经被遍历过，也continue q[ ++ tt] = {a, b}; //剩下来的都是精华，开始操作 pre[a][b] = t; //记录( a , b )状态是从哪来的 } } } int main() { scanf("%d", &n); for (int i = 0; i < n; i ++ ) for (int j = 0; j < n; j ++ ) scanf("%d", &g[i][j]); bfs(n - 1, n - 1); //！！！这里我们很巧妙的从终点开始bfs找起点，这样的话pre数组就倒着存了，输出的时候从起点开始沿着pre数组输出就行了！！！ PII end(0, 0); while (true) { printf("%d %d\n", end.x, end.y); if (end.x == n - 1 && end.y == n - 1) break; end = pre[end.x][end.y]; } return 0; } 来源：B3626 跳跃机器人
简单的说就是有一条线性的箱子，1 到 n ，从 1 出发，每次可以选择 +1 ，或者 -1 ，或者翻倍。问最短几步到 n
一道很简单BFS题目，但是我一开始想的是用DFS，发现不管怎么整都很难处理不断的 +1 再 -1这个问题。
后来一想到，求最短路啊，BFS啊！
如果吧所有的选择看成一颗三叉树，那么为 n 的叶子节点的最小深度就是答案。如果用DFS做需要求出所有情况然后比较最小深度，然而如果用BFS的话 n 节点第一次入队列就一定是最小深度了。
芜湖 ~ ~
再举个最短路的例子
例：AcWing 1100. 抓住那头牛
不难，每次走+1，-1，*2，很明显是bfs最短路，但是要注意好边界问题。
#include <cstring> #include <iostream> #include <algorithm> using namespace std; const int N = 1e5 + 10; int n, k; int q[N]; int dist[N]; int bfs() { memset(dist, -1, sizeof dist); dist[n] = 0; q[0] = n; int hh = 0, tt = 0; while (hh <= tt) { int t = q[hh ++ ]; if (t == k) return dist[k]; if (t + 1 < N && dist[t + 1] == -1) { dist[t + 1] = dist[t] + 1; q[ ++ tt] = t + 1; } if (t - 1 >= 0 && dist[t - 1] == -1) { dist[t - 1] = dist[t] + 1; q[ ++ tt] = t - 1; } if (t * 2 < N && dist[t * 2] == -1) { dist[t * 2] = dist[t] + 1; q[ ++ tt] = t * 2; } } return -1; } int main() { cin >> n >> k; cout << bfs() << endl; return 0; } 7.多源BFS
源点有多个
例：AcWing 173. 矩阵距离
需要求的图上所有的点到离ta最近的源点的距离
之前在洛谷上我也做到过类似的题目，我最开始想通过记忆化搜索和递归来实现，但是还是容易TLE
最后发现正解其实是BFS，初始把所有的源点都放进队列，每次往外BFS一层一层的搜，由于BFS的最短路特性，每个点只被更新一次，且更新为最短距离答案。
这样相当于设置了一个虚拟的超级源点，这个超级源点到每个普通源点的边权都是0，然后从这个超级源点把其他所有的普通源点拓展进队列。
！这里求最短路不用像dijstra一样初始化距离为无穷，因为BFS每个点只被更新一次，所以只需要把dist[ ] [ ] 更新成一个特殊值就可以了，如 - 1。
#include <cstring> #include <iostream> #include <algorithm> #define x first #define y second using namespace std; typedef pair<int, int> PII; const int N = 1010, M = N * N; int n, m; char g[N][N]; PII q[M]; int dist[N][N]; void bfs() { int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}; memset(dist, -1, sizeof dist); int hh = 0, tt = -1; for (int i = 1; i <= n; i ++ ) for (int j = 1; j <= m; j ++ ) if (g[i][j] == '1') { dist[i][j] = 0; q[ ++ tt] = {i, j}; } while (hh <= tt) { auto t = q[hh ++ ]; for (int i = 0; i < 4; i ++ ) { int a = t.x + dx[i], b = t.y + dy[i]; if (a < 1 || a > n || b < 1 || b > m) continue; if (dist[a][b] != -1) continue; dist[a][b] = dist[t.x][t.y] + 1; q[ ++ tt] = {a, b}; } } } int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; i ++ ) scanf("%s", g[i] + 1); bfs(); for (int i = 1; i <= n; i ++ ) { for (int j = 1; j <= m; j ++ ) printf("%d ", dist[i][j]); puts(""); } return 0; } 7.1 洛谷BFS多源最短路
有一个要注意的地方，就是个g[ ] [ ]不用初始化为一个很大的数，因为每个点只会被更新一次不会被更新多次，所以只要是一个特殊值就可以了，此处是初始化为-1。
来源：P1332 血色先锋队
本来我以为这是一道DFS的题目，但是TLE了六个测试名，可恶，当我苦思冥想如何能更好的记忆化搜索的时候，没想到标签的正解是BFS。呜呜呜，确实好用啊
联通块是DFS，但是关于图上的最短路还是建议BFS。
这道题用DFS，每次从感染源出发，然后更新最小值的话会让一些点被重复更新，然后就TLE了。
我本来还在想如果从首领开始反向记忆化搜索DFS可能可以？但是那样子太复杂了，而且感觉还是很容易T。
但没事BFS就不一样了，BFS从每个感染源开始往外一层一层的搜，每个点只需要经过一次，因为第一次被搜到一定是这个点最快被感染的时间。
还有就是我在上一篇的心得里学到了用结构体些BFS 的这个好方法，在元素不止一个的时候就很好用。
const int N = 550; int g[N][N],st[N][N]; int n,m,a,b,c,d; int turnx[8] = {1,-1,0,0}; int turny[8] = {0,0,1,-1}; struct Node { int x,y,d; }point; queue<Node> q; void bfs() { int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1}; //定义方向向量一共四个方向 while(!q.empty()) { auto t=q.front(); q.pop(); for(int i=0;i<4;i++) { int xx=t.x+dx[i],yy=t.y+dy[i]; if(xx>=1 && xx<=n && yy<=m && yy>=1 && st[xx][yy] == 0) { st[xx][yy] = 1; point.x = xx; point.y = yy; point.d = t.d+1; g[xx][yy] = point.d; q.push(point); } } } } signed main() { cin>>n>>m>>a>>b; memset(g,-1,sizeof(g)); for(int i=1; i<=a; i++){ cin>>c>>d; g[c][d] = 0; st[c][d] = 1; q.push((Node){c,d,0}); } bfs(); for(int i=1; i<=b; i++){ cin>>c>>d; cout<<g[c][d]<<endl; } } 8.最小步数模型
在算法基础课的时候讲过一道题：
AcWing 845. 八数码
这道题是一个3 × 3的九宫格，每次可以让棋盘上的 x 与上下左右交换，最后让棋盘上的数字变成顺序。
这道题就是最小步数模型，我们把每种棋盘的情况看成一种状态。
用bfs写需要有两个东西：一个是队列，一个是存储dist。
但是这道题难的地方就在：1.状态表示复杂。2.如何记录每个状态的路径的距离。
- 1.首先我们可以用字符串string来存储数字顺序以表示图的状态，所以队列可以写 queue< string > q
- 2.用映射哈希表unodered_map< string , int > dist
code:
#include <iostream> #include <algorithm> #include <unordered_map> #include <queue> using namespace std; int bfs(string state) { queue<string> q; unordered_map<string, int> d; q.push(state); d[state] = 0; int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}; string end = "12345678x"; while (q.size()) { auto t = q.front(); q.pop(); if (t == end) return d[t]; int distance = d[t]; int k = t.find('x'); //STL里的函数！ int x = k / 3, y = k % 3; //一个小技巧，负责一维位置转换到二维图上的位置 for (int i = 0; i < 4; i ++ ) { int a = x + dx[i], b = y + dy[i]; if (a >= 0 && a < 3 && b >= 0 && b < 3) { swap(t[a * 3 + b], t[k]); //二维转换回一维 if (!d.count(t)) //如果之前没有搜到过，那么这就是新的状态，加入队列里 { d[t] = distance + 1; q.push(t); } swap(t[a * 3 + b], t[k]); } } } return -1; //如果宽搜到不了终点说明是NO } int main() { string state; for (int i = 0; i < 9; i ++ ) { char s; cin >> s; state += s; } cout << bfs(state) << endl; return 0; } —————————————————————————————————————
例：AcWing 1107. 魔板
这道题有三种操作A，B，C，需要按照字典序来输出操作顺序。
我们只需要在每次拓展的时候A,B,C依次去操作就可以了。
因为A在B前，B在C前，在拓展占到之后同一个状态的时候，一定是也是先由在前面的拓展到，一个状态只被更新一次，所以通过数学归纳法可知最后得到的结果一定也是按照字典序的。
举例：—A，—B, —C，再队列里A先出队列，当拓展到某个状态S，那么B,C作为非最优解已经无法更新被更新的状态S了，始终保持这样的字典序最小，我们最后的答案也是最典型最小了。
这个和BFS的最短路原理很像。
！！我们可以发现BFS队列两段中的一段，比如x x x x x ，这一段虽然dist都是 x ，但是实际上他们的拓展顺序是不同的，在这里也就对应着他们是从不同的ABC顺序排列得到的。
code：
#include <cstring> #include <iostream> #include <algorithm> #include <unordered_map> #include <queue> using namespace std; char g[2][4]; unordered_map<string, pair<char, string>> pre; unordered_map<string, int> dist; void set(string state) { for (int i = 0; i < 4; i ++ ) g[0][i] = state[i]; for (int i = 7, j = 0; j < 4; i --, j ++ ) g[1][j] = state[i]; } string get() { string res; for (int i = 0; i < 4; i ++ ) res += g[0][i]; for (int i = 3; i >= 0; i -- ) res += g[1][i]; return res; } string move0(string state) { set(state); for (int i = 0; i < 4; i ++ ) swap(g[0][i], g[1][i]); return get(); } string move1(string state) { set(state); int v0 = g[0][3], v1 = g[1][3]; for (int i = 3; i > 0; i -- ) { g[0][i] = g[0][i - 1]; g[1][i] = g[1][i - 1]; } g[0][0] = v0, g[1][0] = v1; return get(); } string move2(string state) { set(state); int v = g[0][1]; g[0][1] = g[1][1]; g[1][1] = g[1][2]; g[1][2] = g[0][2]; g[0][2] = v; return get(); } int bfs(string start, string end) { if (start == end) return 0; queue<string> q; q.push(start); dist[start] = 0; while (!q.empty()) { auto t = q.front(); q.pop(); string m[3]; m[0] = move0(t); m[1] = move1(t); m[2] = move2(t); for (int i = 0; i < 3; i ++ ) if (!dist.count(m[i])) { dist[m[i]] = dist[t] + 1; pre[m[i]] = {'A' + i, t}; q.push(m[i]); if (m[i] == end) return dist[end]; } } return -1; } int main() { int x; string start, end; for (int i = 0; i < 8; i ++ ) { cin >> x; end += char(x + '0'); } for (int i = 1; i <= 8; i ++ ) start += char('0' + i); int step = bfs(start, end); cout << step << endl; string res; while (end != start) { res += pre[end].first; end = pre[end].second; } reverse(res.begin(), res.end()); if (step > 0) cout << res << endl; return 0; } 9. BFS洛谷题
9.1 求先序排列
来源：P1030 求先序排列
一道给中序和后序遍历求前序的题，希望做法可以获得一点点的启发
string up,down; void build(int l1,int r1,int l2,int r2) { if(l1>r1)return; cout<<down[r2]; int t = l1; while(up[t] != down[r2])t++; int ant=t-l1; build(l1,t-1,l2,l2+ant-1); build(t+1,r1,l2+ant,r2-1); } signed main(){ TLE; cin>>up>>down; int n=up.size()-1; build(0,n,0,n); } 9.2 BFS更新顺序
来源：F 迷失的Syuggie
一道很简单的bfs，但是我一直出错。
错误点：
void bfs() { memset(d,-1,sizeof d); d[xs][ys]=0; q.push({xs,ys}); int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1}; //定义方向向量一共四个方向 while(!q.empty()) { auto t=q.front(); q.pop(); for(int i=0;i<4;i++) { int x=t.first+dx[i],y=t.second+dy[i]; if(x>=1 && x<=n && y<=m && y>=1 && g[x][y]!='#' && d[x][y]==-1 ) { //cout<<"x: "<<x<<"y: "<<y<<endl; if(d[t.first][t.second] >= k)continue; d[x][y]=d[t.first][t.second]+1; q.push({x,y}); ans=min(ans,abs(x-xt) + abs(t.x-yt)); //错误点1：仔细看会发现这样ans根本没有计入起点对应的距离值，当起点作为最优解的时候答案就错了 //错误点2：因为ans取值在for循环里，如果循环没有成立甚至不会取值，所以即使改成： //ans=min(ans,abs(t.first-xt) + abs(t.second-yt)); //如果循环一步都没成立直接跳过，也没有计入到上一个点的距离值。 //所以标准写法是把ans=min(ans,abs(t.first-xt) + abs(t.second-yt)); //写在for循环前面 } } } } 10. DFS+BFS拓展
10.1 可回头的迷宫，一个节点可能会走不止一次
来源：P2802 回家
这道题有一个特殊的地方：一个节点可能会走不止一次。
因为有时候需要绕远路去吃鼠标回血才能继续往下走，不然的话可能会导致因为生命值不够而到不了终点，所以最优解反而是需要先去吃个鼠标然后回来继续走。
题解的做法有BFS和DFS。
总结：其实不管是DFS还是BFS，这道题都是在模板上增加了一个关键改动：
即把原先 visit 数组表示的是访问过和没有访问过 变成了 上次访问到这个点的时候生命值是多少，如果比上一次访问到这个点的生命值还要小，那么一定不是最优解。
先看BFS的做法：
大佬的tips：
1.bfs求最短路这里就不解释了。关键是一些本题特有的判断。首先，因为0代表障碍，所以我们可以将外面memset成0，然后照样读入就行了。然后再bfs时，连同原本的障碍物一同判掉就可以了。 2.另外，血量也是个神奇的东西。考虑到，如果你的血量只剩1了，而此时你还没有完成任务，那么你无论再怎么走都是GAMEOVER的。所以，血量剩1时，直接就跳出就行了。 3.如何判重呢？如果不判重，那么就可能会陷入无限的死循环……而此题又难以直接用是否到过一点判重，例如下图： #020 #010 #010 #010 #410 #013 ##那么，唯一可以完成任务的路线是：(1,2)->(2,2)->(3,2)->(4,2)->(5,2)->(5,1)->(5,2)->(6,2)->(6,3)。 可以发现，点(5,2)是被走了两次的！所以，如果按传统方式判重就会WA。 那么，如何判重呢？我们可以引入一点贪心的思想。我们可以将visit数组从bool型转为int型，存储目前到达它的路径中，到达它时血量最多的一次的血量。因为是bfs，所以简单的证明可以知道，如果一条路径到达一个已经到达过的点，且血量还小于等于visit时，那么即使完成了任务，其步数也不会时最优的。反之，如果到达一个点，其血量值可以更大，那么这就一种可能的路径，并不是重复到达。这样，就可以既保证了答案得正确性，又保证了不会TLE。 1.题主用的是结构体的队列，在push的时候他用到了一个新手法：强制转化
wz.push((NODE){sx,sy,0,6});//推入队列，这里用了强制类型转换 很值得学一下 2.我来解释一下为什么走到重复的点可以直接更新其 vist 数组存的值：
- 当一个走到了一个结点并把它加入队列，如果要让这个节点第二次被加入队列一定是从这个节点 走出去 然后 再走回来，那么就和第一次入队一定不是一层。这是BFS写法，所以当我们第二次走到一个结点改变它的 vist 的时候，第一次入队列的这个节点一定是已经遍历过了，所以就不会影响之前的操作。
- 再说说如果从一个结点走向不同的路径最后回来会不会冲突：首先，如果从一个结点走出去捡不到鼠标我们是直接不会入队的，所以一定是捡到了鼠标。如果从两条路走出去，回来的时候不是同一层，那么可以看做第 n 次走到和第 n + 1次走到，和上述是没有区别。如果从两条路走出去，回来的时候是同一层的，那么这个节点分别入队的两次步数记录其实是一样的，下次遍历到这个节点的时候相当于是用生命值更大的可能路径覆盖了生命值小的，相当于忽略了生命值小的那条路。也不会影响最后的答案。
#include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<string> #include<cmath> #include<queue> using namespace std; int jz[20][20]={0};//存储原地图 struct NODE//一个节点，即一个状态 { int x,y,bs,xl;//位置，步数与血量 }qc,fr; int zl[4][2]={{0,1},{0,-1},{1,0},{-1,0}};//增量，即向四周可能走的位置 int visit[20][20]={0};//visit int版数组 queue<NODE>wz;//bfs队列 int main() { int n,m; scanf("%d%d",&n,&m); int sx,sy; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { scanf("%d",&jz[i][j]); if(jz[i][j]==2)sx=i,sy=j;//记录出发位置 } wz.push((NODE){sx,sy,0,6});//推入队列，这里用了强制类型转换 visit[sx][sy]=6;//初始位置设置其visit值 bool tf=true;//判断是否完成任务，tf==false即完成 while(!wz.empty() && tf)//直到完全失败或成功 { qc=wz.front();//取队列最前面的节点 wz.pop();//弹出队列 if(qc.xl==1)continue;//如果血量为1，则继续 for(int i=0;i<4 && tf;i++)//四个方向 { if(jz[qc.x+zl[i][0]][qc.y+zl[i][1]])//如果可以到达 if(visit[qc.x+zl[i][0]][qc.y+zl[i][1]]<qc.xl-1)//如果血量更大 { fr.x=qc.x+zl[i][0]; fr.y=qc.y+zl[i][1]; fr.bs=qc.bs+1;//更新新的节点 fr.xl=jz[fr.x][fr.y]==4?6:qc.xl-1;//如果下一个节点是有鼠标的，那么有变成6 visit[fr.x][fr.y]=qc.xl-1;//更新visit if(jz[fr.x][fr.y]==3)tf=false;//如果任务完成，那么tf更新 wz.push(fr);//加入队列 } } } if(tf)printf("-1");//如果任务失败 else printf("%d",fr.bs);//如果任务成功，则输出结果 return 0; } 然后来看看DFS的写法：
#include <bits/stdc++.h> using namespace std; const int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1}; int a[10][10],book[10][10][8],n,m,sx,sy,ans=INT_MAX; void dfs(int x,int y,int step,int hp) { if(a[x][y]==3) { ans=step; return; } if(a[x][y]==4)hp=6; if(hp<=1||step>=ans||a[x][y]==0||step>=book[x][y][hp])return; book[x][y][hp]=step; for(int i=0;i<4;i++) { int nx=x+dx[i],ny=y+dy[i]; dfs(nx,ny,step+1,hp-1); } return; } int main() { cin>>n>>m; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { cin>>a[i][j]; if(a[i][j]==2)sx=i,sy=j; } } memset(book,0x3f,sizeof(book)); dfs(sx,sy,0,6); if(ans<INT_MAX)cout<<ans; else cout<<"-1"; return 0; } 10.2 搬运值找上下界
来源：P1025 [NOIP2001 提高组] 数的划分
这是一道经典的题，将总和为 n 的数分成 k 份，只改变顺序视作一种【如：1 1 5 和 1 5 1 和 5 1 1 看做一种】
求可以分成多少种
这道题的数据并不是很大，所以我想用dfs，先从所有的权值都在最后一份上开始，然后把权值不断往前面的份数搬运。但是这么写很复杂，并且很容易TLE
！！！这个时候从题解发现了一些点：
- 因为我们在往前搬运权值的过程中要避免往前搬运的太多，反而后面的权值小了，这样会导致出现和之前重复的方案。这个时候我们可以发现，避免重复我们其实是可以保证这一层的数一定是小于等于下一层的数的。所以我们就保证了DFS的下届。
- 然后我们来确定搜索的上届。我们可以发现因为要保持每一层是小于等于下一层的，所以当前层数的最大值其实是剩下的层数平分的权值，再大就不符合了。
- 综上所述我们确定了上届和下届，这样用这道简单的题就可以AC了.
- 关于这道题题解有多种解法，除了上面讲述的DFS，还有用DP思想解答的，还有用母函数的思想解答的，还有用递推解答的，还有用数学规律的。附加一个用母函数解答这道题的大佬的题解博客;https://www.luogu.com.cn/blog/hardictdbsd/solution-p1025
关键代码：
const int N=220; int n,k; int st[N]; int ans; void dfs(int u,int mark,int sum){ if(u == k && sum == n){ans++;return;} if(u >= k)return; for(int i=mark; i <= (n-sum) / (k-u); i++) { dfs(u+1,i,sum+i); }return; } int main() { TLE; cin>>n>>k; for(int i=1; i<=n; i++)dfs(1,i,i); cout<<ans<<endl; return 0; } 10.3 鼠鼠找奶酪
【天空是蔚蓝色，窗外有千纸鹤】
太痛了，写了一个晚自习的代码，嘤嘤嘤。
来源：P3958 [NOIP2017 提高组] 奶酪
满分算法
- 搜索算法—深度优先
其实深度优先应该是最快的。
首先，我们找出所有可以从下表面进入的球，然后深度优先搜一遍。一旦遇到一个点最高处高度 z+r≥h z+r≥h，就表示可以到上表面，退出。因为每个洞最多访问一次（只需要求是否能到达上表面，而不是最短步数），然后决定下一步的时候还需要O(n)O(n)的时间。所以总复杂度时O(n2)O(n2)。
实际上，往往不需要访问所有的洞就可以判断“Yes”，大多数情况下只有“No”的情况要访问全部。因此很少达到O(n2)O(n2)的最高复杂度。
- 搜索算法—广度优先
同上思想，但是初始时不是对于每个点跑一遍，而是把所有与下表面接触的洞直接加入广搜队列，然后搜索。复杂度仍然是O(n2)O(n2)。细节同上，但是往往跑的量比DFS更大。
- 并查集算法
我们可以为每一个球都建立一个结点，然后用O(n2)O(n2)的时间完成并查集处理，最后查询 与下表面接触的球体中 是否有和 与上表面接触的球体 在同一个集合中 的球体（有些拗口，理解就好）。然后输出“Yes”或“No”。这个算法应该常数略大，因为总是要跑完所有n2n2次连接。
因为前段我写生成树写魔怔了，所以没选择简单的DFS写法，而是并查集写法，然后出现了很多很多的错误。
我最开始想用先建边，然后通过并查集记录一个集合的最低点和最高点，如果上下都满足就输出Yes。这样写会复杂的多，相反大佬的思路甚至都没有建边，而是巧妙的通过并查集解决了问题。
大佬的思路：
用的是直接输入所有的点，存入和最下面通路的点，存入和最上面通路的点，然后对所有的点执行并查集，如果两个点之间是相通的，那么就统一根节点。 最后判断一下最下面的数组和最上面的数组是否存在一对根节点一样的，那么就是相通的了，输出Yes即可。
还有就是最后判断的时候如果写：
if( fa[ down[i] ] == fa[ up[j] ] ){cout<<"Yes"<<endl;return;} 会 Wa #5#6#7，改成 find 函数就AC了，我觉得可能还是我之前说的那个问题，就是一个集合的根节点 fa数组 值改变的时候，原先的子节点 fa 数组值没来得及更新。
AC并查集代码： const i#nt N = 1e3+10; int n, m, idx, idy, h, r; struct node{ int u; int v; int w; }e[10000001]; int x[N],y[N],z[N],down[10000001],up[10000001]; int fa[N], cnt, ans, num, ant; bool cmp(node x, node y){return x.w < y.w;} int find(int x){return fa[x] == x ? fa[x] : fa[x] = find(fa[x]);} void kruskal(){ for(int i=1; i<=m;i++) { for(int j=i; j<=m; j++) { if(i == j)continue; if(x[i] == x[j] && y[i] == y[j] && z[i] == z[j])continue; if(4*r*r < (x[i] - x[j]+0.0)*(x[i] - x[j]+0.0) + (y[i] - y[j]+0.0)*(y[i] - y[j]+0.0))continue; //这里是大佬的写法，据说是如果只看x和y就已经超过了就直接continue，防止爆long long if(4*r*r >= (x[i] - x[j]+0.0)*(x[i] - x[j]+0.0) + (y[i] - y[j]+0.0)*(y[i] - y[j]+0.0) + (z[i] - z[j]+0.0)*(z[i] - z[j]+0.0)) { int markx = find(i); int marky = find(j); if(markx == marky)continue; fa[markx] = marky; } } } } void solve() { idx=0,idy=0; cin>>m>>h>>r; sfor(i,m)fa[i] = i; sfor(i,m){ cin>>x[i]>>y[i]>>z[i]; if(z[i] - r <= 0)down[++idx] = i; if(z[i] + r >= h)up[++idy] = i; } kruskal(); for(int i=1; i<=idx; i++){ for(int j=1; j<=idy; j++){ if( find( down[i] ) == find( up[j] ) ){cout<<"Yes"<<endl;return;} } }cout<<"No"<<endl; } signed main() { int t;cin>>t; while(t--)solve(); } 10.4 高精度乘法+DFS(floyd)
来源：P1037 [NOIP2002 普及组] 产生数
没啥难度，多了一个高精度
10.5 遍历每个顶点作为祖宗结点，以此找到最优路径
来源：P1294 高手去散步
求所有完整路径的最长路
由于我们未知谁是根节点，所以我们用一个循环遍历所有的点作为根节点。然后分别DFS求最长路。
得到最大的答案。
10.6 方向向量搜索导致数组越界
我相信你写图论一定经常需要按照网格走上下左右，于是乎会经常用到以下这种写法：
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};for(int i=0;i<4;i++){int x=t.first+dx[i];int y=t.second+dy[i];if(x>=1&& x<=n && y<=n && y>=1&& g[x][y]=='0'&& d[x][y]==-1){//注意！这里的if判断一定要先判断边界然后再判断后边的俩//如果颠倒了顺序可能会导致因为范围超过而有了数组越界的错误}}10.7 手动模拟队列
来源：P1747 好奇怪的游戏
这道题不难，有趣的是题解分STL自带的queue写法和模拟的queue写法两种
这两种方法关于压入队列和清空的部分有一些差别
STL code：
#include<iostream> #include<queue> //使用STL队列的头文件 #include<cstring> using namespace std; int x1,y1,x2,y2; struct node{ int x,y; int s;//s即step步数 }; //棋盘上一个点定为一个整体，x y为坐标，s为到这点所需最短步数 int dx[12]={2,2,-2,-2,-1,-1,1,1,-2,-2,2,2}; int dy[12]={2,-2,2,-2,-2,2,-2,2,1,-1,1,-1}; //枚举田字、日字的12种走法 bool b[1000][1000]; //记录点是否走过，防止重复拓展 queue<node> q; //定义一个队列，类型为node，queue是关键字，< >里填变量类型，也可以是int、float等等，q是队列名 int bfs(int x,int y) //广搜函数，x y为起点坐标 { node a; a.x=x,a.y=y,a.s=0; q.push(a); //先初始化，把起点步数设为0，放入队列，用STL是不是很方便简洁 do{ a=q.front(); //引用队首元素，注意并不删除 q.pop(); //队首元素出队 for(int i=0;i<12;i++) //枚举12种走法 { node c; //c记录下一步走到的点 c.x=a.x+dx[i],c.y=a.y+dy[i]; if(c.x>=1 && c.y>=1 && b[c.x][c.y]==false) { if(c.x==1 && c.y==1){ return c.s; //到（1,1）就直接返回结果 } b[c.x][c.y]=true; //记录此点已走过 c.s=a.s+1; //这一点的最短步数=上一层（也就是拓展出它的那个点，点a）的最短步数+1步 q.push(c); //把新拓展的c点放入队列 } } }while(!q.empty()); //当队列不为空时继续 } int main() { cin>>x1>>y1>>x2>>y2; cout<<bfs(x1,y1)<<endl; //第一匹马 memset(b,0,sizeof(b)); while(!q.empty()) q.pop(); //千万记得b这个标记数组要清零，而且搜到（1，1）时队列可能还没空，要清空 cout<<bfs(x2,y2); //第二匹马 return 0; } 还有一种压入的方法：
struct Node { int x,y,step ; Node (int a=0,int b=0,int c=0) //写一个析构函数 { x=a;y=b;step=c; } }; q.push((Node){x,y,0});//压入队列写法1 q.push(Node(ex,ey,cur.step+1));//压入队列写法2 模拟queue code：
#include <cmath> #include <cstdio> #include <cstring> #include <cstdlib> #include <iostream> #include <algorithm> using namespace std;//头文件 bool vis[105][105]; int X,Y; int dx[15]={-2,-1,1,2,2,2,2,1,-1,-2,2,-2}, dy[15]={2,2,2,2,1,-1,-2,-2,-2,-2,1,-1};//因为有十二个方向，所以要写两个方向增量。 struct Node { int x,y; int step; }queue[1100];//结构体，分别保存(x,y)，和当前最小步数。 void bfs(int X,int Y) {//开始搜！！！ int head=0,tail=1,nx,ny;//head为头指针，tial为尾指针，nx为新的点的X轴，ny为新的点的Y轴。 queue[1].x=X; queue[1].y=Y; queue[1].step=0; vis[X][Y]=true;//初始化。 while (head<tail) { head++; for (int i=0;i<12;i++) {//枚举十二个点。 nx=queue[head].x+dx[i]; ny=queue[head].y+dy[i]; if ((nx>=1&&nx<101)&&(ny>=1&&ny<101)&&vis[nx][ny]==false) { //判断这个点是否可取。 tail++; queue[tail].x=nx; queue[tail].y=ny; queue[tail].step=queue[head].step+1; vis[nx][ny]=true;//保存这个点，以及步数。 if (nx==1&&ny==1) {//判断是否到达了终点。 printf ("%d\n",queue[tail].step);//输出 return; } } } } return;//好习惯。 }27 int main () { scanf ("%d%d",&X,&Y); bfs (X,Y); memset (vis,false,sizeof(vis));//注意一定要重新初始化！！！ scanf ("%d%d",&X,&Y); bfs (X,Y); return 0; } 10.8 小错误点
来源：B3624 猫粮规划
纯纯的大水题，但是有一个点要注意，就是当搜到一个点符合[ l , r ] 的时候 ans++ ，但是别 return 。因为可能接下来多选几个点还在这个区间里。
还有就是要剪枝，不然TLE。
10.9 小做题心得
来源：P3111 [USACO14DEC] Cow Jog S
纯纯的大水题，但是这边的建议是最好还是先对 t 秒后每头牛能到的地方进行一个预处理， 然后直接快乐的for循环从后往前看，前者的最后位置是否大于后者就行，别忘了前者大于后者的时候更新前者的最后位置，然后ans++
10.10 DFS+素数筛
来源：P7200 [COCI2019-2020#1] Lutrija
这道题懂点小心思可以发现只有几种特殊情况，只需要考察x-2/x+2 , y-2/y+2 是不是素数，然后把情况分开就行，我是直接暴力打表了。哈哈哈
#include<bits/stdc++.h> using namespace std; #define TLE ios::sync_with_stdio(0),cin.tie(0) #define ll long long #define endl "\n" #define out(a) cout<<a; #define put(a) cout<<a<<'\n'; #define qfor(i,n) for(long long i=0;i<n;i++) #define sfor(i,n) for(long long i=1;i<=n;i++) #define int long long typedef pair<int,int>PII; typedef priority_queue<int,vector<int>,greater<int>>pri_int; const int N=200005; int mod = 1e8; bool is_prime(long long x){ //素数筛子 if(x==1) return false; if(x==2) return true; if(x%2==0) return false; for(long long i=3;i*i<=x;i+=2) if(x%i==0) return false; return true; } int tank[N]; int n, m; void solve() { cin>>n>>m; int ans=0; if(is_prime(abs(n-m))){cout<<2<<endl<<n<<' '<<m<<endl;return;} if(n==2 && m==2){cout<<-1<<endl;return;} if(n==2){ if(is_prime(m+2)){cout<<3<<endl<<n<<' '<<m+2<<' '<<m<<endl;return;} else {cout<<-1<<endl;return;} } if(m==2){ if(is_prime(n+2)){cout<<3<<endl<<n<<' '<<n+2<<' '<<m<<endl;return;} else {cout<<-1<<endl;return;} } if(is_prime(n-2))ans+=1; if(is_prime(n+2))ans+=2; if(is_prime(m-2))ans+=4; if(is_prime(m+2))ans+=8; if(ans==0){cout<<-1<<endl;return;} if(ans==1 || ans==2 || ans==4 || ans==8 || ans==3 || ans==12){cout<<-1<<endl;return;} if(ans==5 || ans==7 || ans==13 || ans==15){cout<<3<<endl<<n<<' '<<2<<' '<<m<<endl;return;} if(ans==9 || ans==11){cout<<4<<endl<<n<<' '<<2<<' '<<m+2<<' '<<m<<endl;return;} if(ans==6 || ans==14){cout<<4<<endl<<n<<' '<<n+2<<' '<<2<<' '<<m<<endl;return;} if(ans==10){cout<<5<<endl<<n<<' '<<n+2<<' '<<2<<' '<<m+2<<' '<<m<<endl;return;} } signed main() { int ___ = 1; //cin>>___; while(___--)solve(); } 10.11 二进制+DFS
来源：B3618 寻找团伙
首先，每个人有若干能力，每个能力偶数人有就作废，奇数人有就算数。
可以想到用二进制01代表每个人是否有某项能力，然后用异或和去做。
这里从题解学到了很多：
- 因为能力最多有60种，显然1<<60不可能，因为1默认是int，长度不够，所以我们需要用1ull，usingnamespace long long 有64位，才能够用.读入每个人的能力时，应该用 p[i] |= (1ULL << (k - x)) 来标记 i 人士拥有 x 能力。需要注意这个 ULL，如果不加，编译器将其视为 int 型的 1，程序会 WA。
- |= 符号快速位运算
- dfs的时候对每个人进行，选，或者不选，最后判断完最后一个人就算是搜到头了。然后比一下max
- 这道题的最优解其实是使用线性基去做，可以让时间复杂度变的很低（这道题的数据并不是很大），有机会去学一下线性基！
输入的时候我们使用：
cin>>n>>m; fup(i,0,n){ int c, x;read(c); fdn(j,c,0){ cin >> x; p[i] |= (1ULL<<(m - x)); } } 比较奇妙的将每个人拥有的能力转化到二进制里了
code：
#include <bits/stdc++.h> using namespace std; typedef unsigned long long ull; ull p[30]; int n, k; void input() { cin >> n >> k; for(int i=0; i<n; i++) { int c, x; cin >> c; while(c--) { cin >> x; p[i] |= (1ULL << (k - x)); // 人士 i 拥有 x 能力，修改对应 bit } } } int choice[30]; ull ans; void dfs(int pos) { if(pos == n) { ull res = 0; for(int i=0; i<n; i++) if(choice[i]) res ^= p[i]; ans = max(res, ans); return; } choice[pos] = 0; dfs(pos + 1); choice[pos] = 1; dfs(pos + 1); } void work() { dfs(0); cout << ans << endl; } int main() { input(); work(); return 0; } 上述代码的复杂度为 O(2n⋅k)，其中 2n为枚举子集的复杂度。
需要指出，本题可以采用线性基 + 贪心来做。线性基能以 O(nk)的复杂度完成任务。
