深度优先搜索

caterpillor 2020-09-25 原文

方法：搜索深度，枚举状态

1.文件夹套文件夹，某些放入扑克牌，请你找出所有有扑克牌的文件夹，并说出你的方法。

2.P1157 组合的输出

#include<bits/stdc++.h>
using namespace std;
int n,r,a[25];
void dfs(int t){
	if(t==r+1){
		for(int i=1;i<=r;i++)
			printf("%3d",a[i]);
		printf("\n");
		return ;
	}
	for(int i=a[t-1]+1;i<=n;i++){
		a[t]=i;
		dfs(t+1);	
	}
}
int main(){
	scanf("%d%d",&n,&r);
	dfs(1);
}

3.P1036 选数

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int a[25],ans,n,k,b[25],c[25],sum;
bool chk(int x){
  for(int i=2;i<=sqrt(x);i++){
    if(x%i==0) return 0;
  }
  return 1;
}
void dfs(int t){
  if(t==k+1){
    if(chk(sum)) ans++;
    return ;
  }
  for(int i=c[t-1]+1;i<=n;i++){
      c[t]=i;//存位置
      sum+=a[i];
      dfs(t+1);
      sum-=a[i];
  }
}
int main(){
  scanf("%d%d",&n,&k);
  for(int i=1;i<=n;i++){
    scanf("%d",&a[i]);
  }
  dfs(1);
  printf("%d\n",ans);
}

4.T113146素数环

#include<iostream>
#include<cstdio>
#include<cmath> 
#include<cstring>
using namespace std;
int n,a[20]={0,1},b[20];
bool chk(int x){
	for(int i=2;i<=sqrt(x);i++){
		if(x%i==0)return 0;
	}
	return 1;
}
void dfs(int t){
	if(t==n+1){
		if(chk(1+a[n])){
			for(int i=1;i<=n-1;i++)
				printf("%d ",a[i]);
			printf("%d\n",a[n]);
		}
		return;
	}
	for(int i=2;i<=n;i++){
		if(!b[i]&& chk(a[t-1]+i)){
			b[i]=1;
			a[t]=i;
			dfs(t+1);
			b[i]=0;
		}
	}
}
int ca=0;
int main()
{
	while(scanf("%d",&n)!=EOF){
		if(ca!=0) printf("\n");
		ca++;
		printf("Case %d:\n",ca);
		dfs(2);	
		memset(b,0,sizeof b);///////////
//		printf("\n");
	} 
}

P2089 烤鸡

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
int sum = 0, n, a[15], cnt, b[100005][15];
void dfs(int t){
  if(sum > n) return;
  if(t == 11){
    if(sum == n){
      cnt++;
      for(int i = 1; i <= 10; i++)
        b[cnt][i] = a[i];
    }
    return;
  }
  for(int i = 1; i <= 3; i++){
    a[t] = i;
    sum += i;
    dfs(t + 1);
    sum -= i;
  }
}
int main(){
  scanf("%d",&n);
  dfs(1);
  printf("%d\n",cnt);
  for(int i = 1; i <= cnt; i++){
    for(int j = 1; j <= 10; j++)
      printf("%d ",b[i][j]);
    printf("\n");
  }

  return 0;
}

二维

P1219 [USACO1.5]八皇后 Checker Challenge

#include<bits/stdc++.h>
using namespace std;
int n,a[15],b[15],l[105],r[105],cnt;
void dfs(int t){
	if(t==n+1){
		cnt++;
		if(cnt>3) return ;
		for(int i=1;i<=n;i++)
			printf("%d ",a[i]);
		printf("\n");
		return ;
	} 
	for(int i=1;i<=n;i++){
		if(!b[i] && !l[t+i] && !r[t-i+n]){
			b[i]=1;
			l[t+i]=1;
			r[t-i+n]=1;
			a[t]=i;//用来存第几行第几列 
			dfs(t+1);
			b[i]=0;
			l[t+i]=0;
			r[t-i+n]=0;
		}
	}
}
int main(){
	scanf("%d",&n);
	dfs(1);
	cout<<cnt<<endl;
}