DFS
1.全排列
#include<bits/stdc++.h>
using namespace std;
int n;
bool st[10];//记录每个数状态
int path[10];//存方案
void dfs(int x)//x表示当前枚举到哪个数
{
if(x > n)
{
for(int i=1; i<=n; i++)
cout << path[i] << ' ';
cout << endl;
return ;
}
for(int i=1; i<=n; i++)
{
if(!st[i])
{
st[i] = true;
path[x] = i;
dfs(x+1);//到下一个位置
st[i] = false;//恢复现场
}
}
}
int main()
{
n = 3;
dfs(1);
}
2.组合
关键在于后面选的数要大于前一位数,保证不重复
#include<bits/stdc++.h>
using namespace std;
int n,r;
int arr[30];//存各种组合
void dfs(int x, int start)//x表示枚举到哪个位置,start代表从哪个数开始
{
if(x > r)
{
for(int i=1; i<=r; i++)
printf("%3d", arr[i]);
printf("\n");
return ;//注意返回,若不返回的话则程序会继续执行下面的语句,也就会进入下一层
}
for(int i=start; i<=n; i++)
{
//不考虑顺序,只考虑组合,无需枚举所有情况
arr[x] = i;//将枚举完的数字填进去
dfs(x+1, i+1);//枚举到下一层
arr[x] = 0;//恢复现场
}
}
int main()
{
cin >> n >> r;
dfs(1,1);//从第一个位置数字1开始枚举
}
3.指数型枚举
每个数有选和不选俩种状态,枚举所有可能性
#include<bits/stdc++.h>
using namespace std;
int n;
bool st[20];
void dfs(int x)
{
if(x > n)//递归到叶子节点
{
for(int i=1; i<=n; i++)
if(st[i]) cout << i << ' ';
cout << endl;
return ;
}
st[x] = true;//选择的状态
dfs(x+1);//递归到下一层
st[x] = false;//不选的状态,也可以理解为恢复现场
dfs(x+1);
}
int main()
{
cin >> n;
dfs(1);
return 0;
}
4.洪水灌溉
#include<bits/stdc++.h>
using namespace std;
const int N = 110;
char g[N][N];
int n,m,ans;
bool st[N][N];
int dx[8] = {-1,-1,0,1,1,1,0,-1};
int dy[8] = {0,1,1,1,0,-1,-1,-1};
void dfs(int x, int y)
{
st[x][y] = true;//标记该坑
for(int i=0; i<8; i++)
{
int a = x+dx[i], b = y+dy[i];
if(a<0 || b<0 || a>=n || b>=m) continue;
if(g[a][b] != 'W') continue;
if(st[a][b]) continue;//如果这坑已经别标记则跳过
dfs(a, b);
}
}
int main()
{
cin >> n >> m;
for(int i=0; i<n; i++)
scanf("%s", g[i]);
for(int i=0; i<n; i++)
for(int j=0; j<m; j++)
{
if(!st[i][j] && g[i][j] == 'W')
{
// cout << i << ' ' << j << endl;
dfs(i, j);
ans++;
}
}
cout << ans << endl;
}