2013年11月12日 星期二

[UVA] 750 - 8 Queens Chess Problem


#include<stdio.h>
#include<string.h>
int c,n,m,o[10],s[10][10]={0},d[10]={0},L[20]={0},R[20]={0};
void dfs(int v){
    int i;
    if(v==8){
        printf("%2d      %d",c++,o[0]+1);
        for(i=1;i<8;i++)
            printf(" %d",o[i]+1);
        puts("");
        return;
    }
    if(v==n-1){
        i=m-1;
        if(d[i]==0 && L[v-i+10]==0 && R[v+i]==0){
            d[i]=1,L[v-i+10]=1,R[v+i]=1;
            o[v]=i;
            dfs(v+1);
            d[i]=0,L[v-i+10]=0,R[v+i]=0;
        }
    }
    else
    for(i=0;i<8;i++){
        if(d[i]==0 && L[v-i+10]==0 && R[v+i]==0){
            d[i]=1,L[v-i+10]=1,R[v+i]=1;
            o[v]=i;
            dfs(v+1);
            d[i]=0,L[v-i+10]=0,R[v+i]=0;
        }
    }
}
int main(){
    int t,i,j,flag=0;
    scanf("%d",&t);
    while(t--){
        c=1;
        if(flag) puts("");
        scanf("%d%d",&m,&n);
        puts("SOLN       COLUMN");
        puts(" #      1 2 3 4 5 6 7 8");
        puts("");
        dfs(0);
        flag=1;
    }
}

沒有留言:

張貼留言