宝贝，生日快乐！！！LevOJ P1220 皇后摆放问题

思路：

深度优先搜索 DFS 。

用 p[10] 存储哪一行摆过了皇后。

如果深度超过 8 ，说明已经棋盘已经摆好了，直接返回。

如果某一行已经摆过了皇后，直接进入下一行。

否则判断这行的每一个位置是否能合法地摆放皇后。

AC代码：

#include<bits/stdc++.h>

using namespace std;

int a[10][10],p[10];
int cnt=0;

bool judge(int x,int y){
    for(int i=1;i<=8;i++){
        if(a[i][y]||a[x][i]){
            return false;
        }
    }
    for(int i=1;i<=8;i++){
        for(int j=1;j<=8;j++){
            if(abs(i-x)==abs(j-y)&&a[i][j]==1){
                return false;
            }
        }
    }
    return true;
}

void dfs(int s){
    if(s>8){
        cnt++;
        return; 
    }
    if(p[s]){
        dfs(s+1);	
    }else{
        for(int i=1;i<=8;i++){
            if(judge(s,i)){
                a[s][i]=1;
                p[s]=1;
                dfs(s+1);
                a[s][i]=0;
                p[s]=0;
            }
        }
    }
}

void solve(int x){
    a[1][1]=x;
    if(a[1][1]){
        p[1]=1;
    }
    for(int i=2;i<=8;i++){
        cin>>a[1][i];
        if(a[1][i]){
            p[1]=1;						
        }
    }
    for(int i=2;i<=8;i++){
        for(int j=1;j<=8;j++){
            cin>>a[i][j];
            if(a[i][j]){
                p[i]=1;
            }
        }
    }
    dfs(1);	
}


int main(){
    int x;
    while(scanf("%d",&x)!=EOF){
        cnt=0;
        memset(a,0,sizeof(a));
        memset(p,0,sizeof(p));
        solve(x);
        cout<<cnt<<endl;
    }
    return 0;
}