NUIST Levoj P1220 皇后摆放问题-526互联

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;
int chess[9][9];
int arr[9][9];
int cnt=0,sum=0;
bool check(int row,int col)
{
for(int i=1;i<9;i++) if(chess[i][col]) return false;
for(int i=row,j=col;i>0&&j>0;i--,j--) if(chess[i][j]) return false;
for(int i=row,j=col;i>0&&j<9;i--,j++) if(chess[i][j]) return false;
return true;
}
void dfs(int row)
{
if(row==9)
{
int n=0;
for(int i=1;i<9;i++)
for(int j=1;j<9;j++)
if(chess[i][j] && arr[i][j])
n++;
if(n==sum) cnt++;
return;
}
for(int i=1;i<9;i++)
if(check(row,i))
{
chess[row][i]=1;
dfs(row+1);
chess[row][i]=0;
}
}
int main()
{
memset(chess,0,sizeof chess);
for(int i=1;i<9;i++)
for(int j=1;j<9;j++)
{
cin>>arr[i][j];
if(arr[i][j]) sum++;
}
dfs(1);
cout<<cnt<<endl;
return 0;
}