AKSZ - 深度优先搜索
2024-05-19 14:55:19
发布于:广东
14阅读
0回复
0点赞
1.排列组合
(1)加法原则 & 乘法原则
(2)排列
- 可以位置不同,但不能重复
- A(m,n) = n * (n - 1) * (n - 2) * ...... * (n - m + 1)
(3)组合
- 不可以位置不同,且不能重复
- C(m,n) = A(m,n) / A(m,m)
2.回溯
- 在递归调用之后执行代码,会从内层往外层
- 枚举排列代码
#include <bits/stdc++.h>
using namespace std;
int n,k,a[11];
bool vis[11];
void dfs(int x)
{
if(x > k)
{
for(int j = 1;j <= k;j++)
{
cout << a[j] << " ";
}
cout << endl;
return;
}
for(int i = 1;i <= n;i++)
{
if(!vis[i])
{
a[x] = i;
vis[i] = 1;
dfs(x + 1);
vis[i] = 0;
}
}
}
int main()
{
cin >> n >> k;
dfs(1);
return 0;
}
3.连通性
- 迷宫问题代码
#include <bits/stdc++.h>
using namespace std;
int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
int n,m,a[41][41];
bool vis[41][41];
bool is_in(int x,int y)
{
return x >= 1 && x <= n && y >= 1 && y <= m;
}
void dfs(int x,int y)
{
vis[x][y] = 1;
for(int i = 0;i < 4;i++)
{
int x2 = x + dir[i][0];
int y2 = y + dir[i][1];
if(is_in(x2,y2) && !vis[x2][y2] && a[x2][y2] == 0)
{
dfs(x2,y2);
}
}
}
int main()
{
cin >> n >> m;
for(int i = 1;i <= n;i++)
{
for(int j = 1;j <= m;j++)
{
cin >> a[i][j];
}
}
dfs(1,1);
if(vis[n][m])
{
cout << "YES" << endl;
}
else
{
cout << "NO" << endl;
}
return 0;
}
4.剪枝(骗分玄学)
- 用法:在程序运行过程中把已不可能得到答案的情况剪掉
- 类别:可行性剪枝、最优性剪枝等
全部评论 1
补充一下八皇后代码
2024-05-15 来自 广东
0
有帮助,赞一个