One day,Li Lei and Han Mei Mei are playing together.

Li Lei says:"Oh~,Dear Mei Mei,Let's play a game,would you like to try?"

Mei Mei says:"Oh~,I'd like to."

Li Lei says:"I will bring a N by N checkerboard and two kinds of queen.Black-queen and White-queen,N of each."

Mei Mei says:"How  are we going to play?,I want to get prepared first."

Li Lei says:"There is no hurry.Let me tell you:you and I each choose one kind of queen and we gonna place them into the board."

"Of cause,there are some principles for you to remember."

1.There shouldn't exist the same kind of queen in the same row and column and also in the diagonal.

2.There may exist some hole on the checkerboard and you can't place queen on it.

3.You should get both queens all placed.

Li Lei smiles badly:"And you gonna tell me how many situations exactly we can success."

Since Mei Mei don't know the size of the board exactly,she comes to you and asks you for help.

She wants you to find out all situations of the checkerboard.

So,try to help Mei Mei.

 

Input:

7 
1 1 1 1 1 1 0  
1 1 1 1 1 1 1  
1 1 1 1 1 1 1  
1 1 1 1 1 1 1
1 1 1 1 1 1 0
1 1 1 1 1 1 1
1 1 1 1 1 1 1 

 

Output

270

ps.1 represents that the place is good and 0 is hole.

S:

It's a classic deep search problem.

We can place the queens row after row.Each row represents a recursion layer.

We don't need to start placing queens after another kind of queen is finished.We can place two kinds of queens simultaneously.

Complete code is given below:

#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
int sum=0,board[100][100],N;
bool rule(int l,int c,int q){
    if(board[l][c]==0||board[l][c]==3||board[l][c]==2)return false;
    for(int i=0;i<l;i++){//we can just go over the board to check if the place is suitable;
        for(int j=0;j<N;j++){
            if(board[i][j]==q){
                if(l-i==abs(j-c)||j==c) return false;
            }
        }
    }
    return true;
}
void dfs(int n){　　　　　　　　　　　//n represents the unfinished row;
    if(n==0) sum++;
    else{
        int i,j,line=N-n;
        for(i=0;i<N;i++){
            if(rule(line,i,2)){　　//2 represents Black-queen and 3 represents White-queen;
                board[line][i]=2;
                for(j=0;j<N;j++){
                    if(rule(line,j,3)){
                        board[line][j]=3;
                        dfs(n-1);
                        board[line][j]=1;
                    }
                }
                board[line][i]=1;
            }
        }
    }
}
int main(){
    cin>>N;
    memset(board,-1,sizeof(board));
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            cin>>board[i][j];
        }
    }
    dfs(N);
    cout<<sum<<endl;
    return 0;
}

What we should take notice of is:

1.memset function can only initialize the array in the form of 0/-1,and be careful when you use sizeof() in a function:the size of the sending array is const 4 (int size).

2.computational thinking:just go over the array if you want to check,instead of calculate in mathmatics.

　In this case,it's reflected in checking the diagonal.

3.debugging:

　1) check the logic.

　2) check ranges of variables.

　3) check the function's variables and it's ability.

4.write clearly before you code.

 

Let's take a little bit about recursive fuctions.

1.recursive export.

2.recursive chain.

When we come to the problems,we should find out the oderly progresses.

Notices are in the debugging.