【题意】这题也是醉了,其实不用怎么剪枝啊,只需要把m==0的情况列个表,还一直以为m==1的时候列表,好毒。
【分析】就是普通的n皇后问题,由于可能有一个点已经有皇后,开始的时候标记就行啦!其实暴力,全部打表也可以,可是还是不会呀!
【AC代码】
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 14;
int vis[4][30];
int ans[14] = {0,1,0,0,2,10,4,40,92,352,724,2680,14200,73712};
int n,m,x,y,sum;
void dfs(int dep)
{
if(dep==n)
{
sum++;
return ;
}
if(vis[0][dep])
dfs(dep+1);
else
{
for(int i=0;i<n;i++)
{
if(!vis[1][i]&&!vis[2][dep-i+n]&&!vis[3][dep+i])
{
vis[1][i]=vis[2][dep-i+n]=vis[3][dep+i]=1;
dfs(dep+1);
vis[1][i]=vis[2][dep-i+n]=vis[3][dep+i]=0;
}
}
}
}
//void dfs(int dep)
//{
// if(dep==n)
// {
// if(m==0)sum++;
// else if(m==1&&C[x]==y)
// {
// sum++;
// }
// }
// else
// for(int i=0;i<n;i++)
// {
// int ok=1;
// C[dep]=i;
// for(int j=0;j<dep;j++)
// {
// if(C[dep]==C[j]||dep-C[dep]==j-C[j]||dep+C[dep]==j+C[j])
// {
// ok=0;
// break;
// }
// }
// if(ok)dfs(dep+1);
// }
//}
int main()
{
while(~scanf("%d%d",&n,&m))
{
if(m==0)
{
printf("%d\n",ans[n]);
continue;
}
if(m==1)scanf("%d%d",&x,&y);
memset(vis,0,sizeof(vis));
if(m==1)
{
vis[0][x]=1;
vis[1][y]=1;
vis[2][x-y+n]=1;
vis[3][x+y]=1;
}
sum = 0;
dfs(0);
printf("%d\n",sum);
}
return 0;
}