12604.c

mail@pastecode.io avatar
unknown
css
a year ago
1.5 kB
4
Indexable
Never
//12604 - N-Queens M-Rooks Problem 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int N, M, cnt=0;

void queen(int *c,int *slash, int *bslash, int *ans, int i);

int main(){
    while(scanf("%d %d", &N, &M) != EOF){
        int c[105]={0}, slash[105]={0}, bslash[105]={0};
        int ans[105]={0};
        cnt = 0;
        queen(c,slash,bslash,ans,0);
        printf("%d\n", cnt);
    }
}

void queen(int *c,int *slash, int *bslash, int *ans, int i){
    if(i >= N+M){

        /*印出來
        for(int ii = 0; ii < N+M; ii++){
            for(int jj = 0; jj < N+M; jj++){
                if(ans[ii]-100 == jj) printf("R");
                else if(ans[ii] == jj) printf("Q");
                else printf("0");
            }
            printf("\n");
        }
        printf("\n\n");
        */

        cnt++;
    }
    else{
        for(int j=0; j<N+M; j++){  //前N項放queen, 後M項放boot
            if(j<N){
                if(c[j] || slash[i+j] || bslash[j-i+N+M]) continue;

                ans[i] = j;
                c[j] = slash[i+j] = bslash[j-i+N+M] = 1;
                queen(c,slash,bslash,ans,i+1);
                c[j] = slash[i+j] = bslash[j-i+N+M] = 0;
            }
            else{
                if(c[j]) continue;

                ans[i] = j+1000;
                c[j] = slash[i+j] = bslash[j-i+N+M] = 1;
                queen(c,slash,bslash,ans,i+1); 
                c[j] = slash[i+j] = bslash[j-i+N+M] = 0;
            }


        }
    }
}