洛谷P1219 [USACO1.5]八皇后 Checker Challenge【搜索回溯】

主对角线 i+j  次对角线  n+i-j

最近学递归回溯..来做做例题.

以前做这题是倒着搜的，下面的代码是正着搜。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define N 20
using namespace std;

int n,cnt;

int ans[N],col[N],c[N*2],d[N*2];

void queen(int now)
{
    if(now==n+1)
    {
        if(cnt<=2)
        {
            for(int i=1;i<=n;i++)
            {
                cout<<ans[i]<<" ";
            }
            cnt++; 
            cout<<endl;
        }else cnt++;
        return ;
    } 
    for(int i=1;i<=n;i++)
    {
        if(!col[i]&&!c[now+i]&&!d[n+now-i])
        {
            col[i]=c[now+i]=d[n+now-i]=1;
            ans[now]=i;
            queen(now+1);
            col[i]=c[now+i]=d[n+now-i]=0;
        }
    }
}
 
int main()
{
    scanf("%d",&n); 
    queen(1);
    cout<<cnt<<endl;
    return 0;
}