C++
| ———————————————深搜——————————————— 深搜也叫深度优先搜索意思是就是一直向前进，直到走不动了，向后退一步，继续前进。这个叫做不撞南墙不回头。 深搜也是dfs：而dfs就像有n个阶段，第n个阶段走不通，就回退到第n-1个阶段尝试其他的可能。 ----- DFS： void dfs(int step){ ---->判断边界 if(...) return; ---->尝试每一种可能 for(int i=1;i<=n;i++){ ... ... ---->继续下一步 dfs(step+1); } } ---- dfs可以解决许多问题比如：数字排列类 （1）排列型枚举：这就是全排列问题 代码实现可以是这样： #include<bits/stdc++.h> using namespace std; int n,a[10],book[10]; void dfs(int x){ //正在第x个格子 if(x>n){ //如果已经放完最后一个格子 for(int i=1;i<=n;i++){ printf("%5d",a[i]); //输出已经放好的数字 } cout<<endl; }else{ //否则继续挑数 for(int i=1;i<=n;i++){ //挑选的范围就是1-n if(book[i]==0){ //如果i没有被用过 book[i]=1; //标记i被用过 a[x]=i; //将i放进a数组的第x个格子 dfs(x+1); //继续搜索下一个格子 book[i]=0; //回溯 把i还回去 } } } } int main(){ cin>>n; dfs(1); //从第1个格子开始放数 return 0; } 第二种组合型枚举： #include<bits/stdc++.h> using namespace std; int n,a[30],book[30],f[30],k,ans;int fun(int x){ //判断质数 if(x==1) return 0; for(int i=2;i<x;i++){ if(x%i==0) return 0; } return 1; } void dfs(int x){ //现在正在第几个格子 if(x>k){ //不需要继续下一个格子 int s=0; for(int i=1;i<=k;i++){ s+=a[i]; } if(fun(s)==1){ //判断目前这种方案是否满足要求 ans++; } }else{ //往格子里面放数 for(int i=1;i<=n;i++){ //可选择的数字范围 if(book[i]==0){ //在f数组的第i个数字没有被用过 book[i]=1; //标记用过 a[x]=f[i]; // 将f[i]存放到数组a中 dfs(x+1); //去下一个格子 book[i]=0; //回溯 把数字还回去 } } } }int main(){ cin>>n>>k; for(int i=1;i<=n;i++){ cin>>f[i]; } dfs(1); //从第一个格子开始 int c=1; //组合数等于排列数除以 k的阶乘 for(int i=1;i<=k;i++){ c=c*i; } cout<<ans/c; return 0; } （3）迷宫类 求起点到终点： #include<bits/stdc++.h> using namespace std; int mat[10][10],book[10][10]; int n,m,t,x,y,sx,sy,fx,fy,ans; int b[4][2]={{-1,0},{1,0},{0,-1},{0,1}}; void dfs(int x,int y){ //挑选下一个格子 （x,y）现在的位置 if(x==fx&&y==fy){ //到达终点 ans++; //方案数加一 }else{ //要继续往后走 //四个方向：上下左右 for(int i=0;i<=3;i++){ int nx=x+b[i][0],ny=y+b[i][1]; //满足三个条件即为可以走 if(mat[nx][ny]==0){ //一、不是障碍物 if(book[nx][ny]==0){ //二、没有走过 if(nx>=1&&nx<=n&&ny>=1&&ny<=m){ //三、没有超过地图边界 book[nx][ny]=1; //标记此位置走过 dfs(nx,ny); //去往这个点继续走 book[nx][ny]=0; //从这个位置退回去 } } } } } } int main(){ cin>>n>>m>>t; cin>>sx>>sy>>fx>>fy; for(int i=1;i<=t;i++){ cin>>x>>y; mat[x][y]=1; } book[sx][sy]=1; //标记起点走过 dfs(sx,sy); //从起点开始搜索 cout<<ans; return 0; } （4）连通块类： 一个连通块就相当于一个迷宫，都是封闭的一块。但是不同的是，迷宫里设有障碍，连通块里没有，可以随意走，并且迷宫的搜索起点和搜索的终点都是确定好的，但连通块的起点可以是随便定的的，所以通常情况下需要遍历多个元素，寻找搜索起点，可能有多个起点。 #include<iostream> using namespace std; char mat[105][105]; int b[4][2]={1,0,0,1,-1,0,0,-1},n,m,ans; void dfs(int x,int y){ //现在在(x,y) for(int i=0;i<=3;i++){ int nx=x+b[i][0]; int ny=y+b[i][1]; if(mat[nx][ny]!='0'&&nx>=1&&nx<=n&&ny>=1&&ny<=m){ mat[nx][ny]='0'; //将与它相邻的细胞都消掉 dfs(nx,ny); } } }int main(){ cin>>n>>m; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cin>>mat[i][j]; } } for(int i=1;i<=n;i++){ //遍历每一个元素 for(int j=1;j<=m;j++){ if(mat[i][j]!='0'){ //找到一个非零元素就开始搜索 mat[i][j]='0'; //将和它连在一起的所有非零元素都标记掉，避免重复计算 ans++; //细胞数量加一 dfs(i,j); } } } cout<<ans; return 0; } |
评论区