深北莫7月30日上午搜索

陌离﹠

2024-07-30 15:36:16

发布于：广东

5阅读

0回复

0点赞

7月30号搜索

全排列问题

#include<bits/stdc++.h> 
using namespace std;
int n;
int a[15];
int e[15];
void d(int x){
	if(x>n){
		for(int i=1;i<=n;i++){ 
			printf("% 5d",a[i]);
		} 
		puts("");
		return;
	}
	for(int i=1;i<=n;i++){ 
		if(!e[i]){
			a[x]=i;
			e[i]=1;
			d(x+1);
			e[i]=0;
		}
	}
} 
int main(){
	scanf("%d",&n); 
	d(1);
}

八皇后 Checker Challenge

/*#include<bits/stdc++.h>
using namespace std;
int a[100001],b[10001],c[100001],d[100001];
int t,n;
int print(){
    if(t<=2){
        for(int i=1;i<=n;i++)
        cout<<a[i]<<" "<<"\n";
    }
    t++;
}
void queen(int i){
    if(i>n){
        print();
        return;
    }
    else{
        for(int j=1;j<=n;j++){
            if((!b[j])&&(!c[i+j])&&(!d[i-j+n])){
                a[i]=j;
                b[j]=1;
                c[i+j]=1;
                d[i-j+n]=1;
                queen(i+1);
                b[j]=0;
                c[i+j]=0;
                d[i-j+n]=0;
            }
        }
    }
}
int main(){    
    cin>>n;
    queen(1);
    cout<<t;
    return 0;
}*/
#include<bits/stdc++.h>
using namespace std;
int a[14],c[3][28]={0},s=0,n;
void e(int l){
    if(l>n){
        s++;
        if(s>3) return;
        else{
            for(int i=1;i<=n;i++) printf("%d ",a[i]);
            printf("\n");
            return;
        }
    }
    for(int i=1;i<=n;i++){
        if((!c[0][i])&&(!c[1][l+i])&&(!c[2][l-i+n])){
            a[l]=i;
            c[0][i]=1; c[1][l+i]=1; c[2][l-i+n]=1;
            e(l+1);
            c[0][i]=0; c[1][l+i]=0; c[2][l-i+n]=0;
        }
    }
}
int main(){
    scanf("%d",&n);
    e(1);
    printf("%d",s);
    return 0;
}

Almost Equal

#include<bits/stdc++.h>
using namespace std;
string s[101],c[101];
int a[101],n,m,p;
void dfs( int k ){
	for( int i = 1 ; i <= n ; i ++ ){
		if( a[i] == 0 ){
			a[i] = 1;
			c[k] = s[i];
			if( k == n ){
				int f = 0,cnt = 0;
				for( int j = 1 ; j < n ; j ++ ){
					cnt = 0;
					for( int k = 0 ; k < m ; k ++ )
						if( c[j][k] != c[j + 1][k] )
							cnt ++;
					if( cnt != 1) f = 1;
				}
				if( !f ) p = 1;
			}
			else dfs( k + 1 );
			a[i] = 0;
			c[k] = "";
		}
	}
}

int main(){
	cin >> n >> m;
	for( int i = 1 ; i <= n ; i ++ )
		cin >> s[i];
	dfs(1);
	if( p ) cout << "Yes";
	else cout << "No";
	return 0;
}

组合的输出

#include<bits/stdc++.h>
using namespace std;
int n,r;vector<int> v;
void dfs(int l,int dep){
    if(dep-1==r){
        for(int i=0;i<r;i++){
            cout<<setw(3)<<v[i];
        }cout<<endl;
        return;
    }
    for(int i=l+1;i<=n;i++){
        v.push_back(i);
        dfs(i,dep+1);
        v.pop_back();
    }
}
int main(){
    cin>>n>>r;
    dfs(0,1);
}

健康的荷斯坦奶牛 Healthy Holsteins

#include<bits/stdc++.h>
#define inf 999999999
using namespace std;
int a[100010],m,n;
int b[101][101],top[100010];
bool p[100010];
int ans=inf,cnt;
int c[100010],coot;
bool pd,flag2;
void dfs(int sum,int h){
    bool f=0;
    for(int i=1;i<=m;i++){
        if(a[i]>0){f=1;break;}
    }
    if(!f){
        if(sum<ans){
            coot=cnt;
            ans=sum;
            for(int i=1;i<=cnt;i++){
                c[i]=top[i];
            }
        }
        return;
    }
    for(int i=h+1;i<=n;i++){
        if(!p[i]){
            p[i]=1;
            for(int j=1;j<=m;j++){
                a[j]-=b[i][j];
            }
            top[++cnt]=i;
            dfs(sum+1,i);
            --cnt;
            p[i]=0;
            for(int j=1;j<=m;j++){
                a[j]+=b[i][j];
            }
        }
    }
}
int main(){
    int i,j,k;
    scanf("%d",&m);
    for(i=1;i<=m;i++){
        scanf("%d",&a[i]);
    }
    scanf("%d",&n);
    for(i=1;i<=n;i++){
        for(j=1;j<=m;j++){
            scanf("%d",&b[i][j]);
        }
    }
    dfs(0,0);
    printf("%d ",coot);
    for(i=1;i<coot;i++){
        printf("%d ",c[i]);
    }
    printf("%d\n",c[coot]);
    return 0;
}

取数游戏

#include<bits/stdc++.h>
using namespace std;
const int N=10,M=256;
int a[N][N],f[N][M],num[M],jump[N];
int T,n,m,ans,tot=0;
int main(){
    for(int i=0;i<(1<<7);i++)if(!(i&(i<<1))){tot++;num[tot]=i;}
    jump[0]=1;jump[1]=2;for(int i=2;i<N;i++)jump[i]=jump[i-1]+jump[i-2];
    scanf("%d",&T);
    for(int ii=1;ii<=T;ii++){
        memset(f,0,sizeof(f));ans=0;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%d",&a[i][j]);
        for(int i=1;i<=n;i++){
            for(int j=1;j<=jump[m];j++){
                int t=num[j];int sum=0;
                for(int l=m;l>=1;l--,t=t>>1)if(t&1)sum+=a[i][l];
                for(int k=1;k<=jump[m];k++){
                    if((num[j]&num[k])||(num[j]&(num[k]<<1))||(num[j]&(num[k]>>1)))continue;
                    else f[i][j]=max(f[i][j],sum+f[i-1][k]);
                }
            }
        }
        for(int i=1;i<=jump[m];i++)ans=max(ans,f[n][i]);
        printf("%d\n",ans);
    }
    return 0;
}

走迷宫

#include<bits/stdc++.h>
using namespace std;
int up[20][20],m,n;
int a,b,c,d;
int s1[120],s2[120],sum=1;
int dir[4][2]={{0,-1},{-1,0},{0,1},{1,0}};
bool flag=false;
void dfs(int x,int y){
	if ((x==c)&&(y==d)){
		cout<<"("<<s1[0]<<","<<s2[0]<<")";
		for (int i=1;i<sum;i++)
		  cout<<"->("<<s1[i]<<","<<s2[i]<<")";
		cout<<endl;
		flag=true;
		return;
	}
	else{
		for (int i=0;i<4;i++){
			int xx=x+dir[i][0],yy=y+dir[i][1];
			if (up[xx][yy]!=0){
				up[xx][yy]=0; 
				s1[sum]=xx;s2[sum]=yy; 
				sum++;
				dfs(xx,yy); 
				sum--;
				up[xx][yy]=1;
			}
		}
	}
}
int main(){
	cin>>m>>n;
	for (int i=0;i<=m+1;i++)
	  for (int j=0;j<=n+1;j++)
	    up[i][j]=0;
	for (int i=1;i<=m;i++)
	  for (int j=1;j<=n;j++)
	    cin>>up[i][j];
	cin>>a>>b>>c>>d;
	up[a][b]=0;
	s1[0]=a;s2[0]=b;
	dfs(a,b);
	if (!flag)
	  cout<<"-1"<<endl;
	return 0;
}

Make Takahashi Happy

#include<bits/stdc++.h>
using namespace std;
int ns,n,m;
int a[110][110];
const int N =1e9+9;
bool b[N];
void dfs(int x,int y){
	if(x==n&&y==m){
		ns++;
		return;
	}
	if(x<n&&!b[a[x+1][y]]){
		b[a[x+1][y]]=1;
		dfs(x+1,y);
		b[a[x+1][y]]=0;
	}
	if(y<m&&!b[a[x][y+1]]){
		b[a[x][y+1]]=1;
		dfs(x,y+1);
		b[a[x][y+1]]=0;
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			cin>>a[i][j];
	b[a[1][1]]=1;
	dfs(1,1);
	cout<<ns;
	return 0;
}