U5-2-DFS-2
原题链接：67324.4.0U5笔记合集
2025-08-20 18:14:02
发布于：江苏
3阅读
0回复
0点赞
1.抽奖5
#include <iostream>
using namespace std;
int a[105], n, b[105];
bool vis[105];
void dfs(int k)
{
if (k > n){
for (int i=1; i<=n; i++) cout<<b[i]<<' ';
cout<<endl;
return ;
}
for (int i=1; i<=n; i++) {
if (vis[i] == 0) {
b[k] = a[i];
vis[i] = 1;
dfs(k+1);
vis[i] = 0; //回溯
}
}
}
int main()
{
cin >> n;
for (int i=1; i<=n; i++) cin>>a[i];
dfs(1);
return 0;
}
2.抽奖6-1
//TLE 第3个点
#include <bits/stdc++.h>
using namespace std;
int a[105], n, m, b[105], ans;
bool vis[105];
bool prime(int x){
if (x<2) return 0;
for (int i=2; i<=sqrt(x); i++)
if (x%i==0) return 0;
return 1;
}
void dfs(int k)
{
if (k > m){
int sum = 0;
for (int i=1; i<=m; i++) {
sum += b[i];
}
if (prime(sum)) {
ans++;
// for (int i=1; i<=m; i++) cout<< b[i]<<' ';
// cout<<endl;
}
return ;
}
for (int i=1; i<=n; i++) {
if (vis[i] == 0) {
b[k] = a[i];
vis[i] = 1;
dfs(k+1);
vis[i] = 0; //回溯
}
}
}
int fac(int y){
int ret = 1;
for (int i=1; i<=y; i++) ret *= i;
return ret;
}
int main()
{
cin >> n >> m;
for (int i=1; i<=n; i++) cin>>a[i]; //积分
dfs(1);
cout << ans/fac(m);
return 0;
}
/*
4 3
3 7 12 19
*/
3.抽奖6-2
#include <bits/stdc++.h>
using namespace std;
int a[105], n, m, b[105], ans;
bool prime(int x)
{
if (x<2) return 0;
for (int i=2; i<=sqrt(x); i++)
if (x%i==0) return 0;
return 1;
}
//从st位置开始抽, 第k次抽奖
void dfs(int st, int k)
{
if (k == m+1) {
int sum = 0;
for (int i=1; i<=m; i++) {
sum += b[i];
}
if (prime(sum)) {
ans++;
}
return ;
}
//从st~n的区间内开始抽
for (int i=st; i<=n; i++) {
b[k] = a[i];
dfs(i+1, k+1);
}
}
int main()
{
cin >> n >> m;
for (int i=1; i<=n; i++) cin>>a[i]; //积分
dfs(1, 1);
cout << ans;
return 0;
}
/*
4 3
3 7 12 19
*/
4.迷宫的入口判断
#include <iostream>
using namespace std;
int mp[105][105];
int n, m, flag;
bool vis[105][105];
int dir[4][2] = {1,0, -1, 0, 0, -1, 0, 1};
void dfs(int x, int y)
{
if (x==n && y==m) { //1.递归出口
flag = 1;
return ;
}
for (int i=0; i<4; i++) { //2. 开始朝四个方向进行搜索
int a = x + dir[i][0];
int b = y + dir[i][1];
if (a<1 || b<1 || a>n || b>m) continue; //越界
if (vis[a][b] || mp[a][b]==1) continue; //已访问 || 障碍物
vis[a][b] = 1;
dfs(a, b);
}
}
int main()
{
cin >> n >> m;
for (int i=1; i<=n; i++) {
for (int j=1; j<=m; j++) {
cin >> mp[i][j];
}
}
dfs(1, 1); //从1,1这个点开始搜索
if (flag) cout<<"YES";
else cout << "NO";
return 0;
}
5.迷宫方案数
#include <iostream>
using namespace std;
int n, m, sx, sy, fx, fy, t, cnt;
int mp[105][105];
int dir[4][2] = {1,0,0,1,0,-1,-1,0};
bool vis[105][105];
void dfs(int x, int y)
{
if (x==fx && y==fy) {
cnt++;
return ;
}
for (int i=0; i<4; i++) {
int a = x+dir[i][0], b = y+dir[i][1];
if (a<1 || b<1 || a>n || b>m) continue;
if (mp[a][b] == 1 || vis[a][b] == 1) continue;
vis[a][b] = 1;
dfs(a, b);
vis[a][b] = 0; //回溯
}
}
int main()
{
cin >> n >> m >> t;
cin >> sx >> sy >> fx >> fy;
while (t--) {
int x, y;
cin >> x >> y;
mp[x][y] = 1;
}
vis[sx][sy] = 1;
dfs(sx, sy);
cout << cnt;
return 0;
}
/*
2 2 1
1 1 2 2
1 2
*/
这里空空如也
有帮助，赞一个