USACOChecker Challenge

http://ace.delos.com/usacoprob2?a=GILo2ACzmVw&S=checker

经典到烂的n皇后问题。。。题目最坑的地方是不能打表。。。

朴素的DFS是绝对不行的，要改，怎么改？最简单的是改判断方法。

这是最朴素的判断函数：

bool check(int dep,int x)
{
    for (int i=1;i<dep;i++)
        if (f[i]==x || f[i]+(dep-i)==x || f[i]-(dep-i)==x)
            return false;
    return true;
}

当n=13时这里成了拖慢整个程序的关键，因为只判断这位置是否可行，而没有理会之后的事情，导致DFS时一直在无目的的寻找。

简单直接的做法是加一个标记数组，直接标记后边不能放皇后的位置，则在DFS时就不会再无目的的寻找了。

void biaoji(int dep,int h,int x)
{
    b[dep][h]+=x;
    for (int i=dep+1;i<=n;i++)
    {
        b[i][h]+=x;
        if (h-(i-dep)>0)
            b[i][h-(i-dep)]+=x;
        b[i][h+(i-dep)]+=x;
    }
}

由于DFS有一个返回操作，标记数组要复位。注意：这里的标记数组一定不能简单的用bool型，因为有些格子会被重复标记，而用bool型复位时无法检测是否被多次标记。

这题还有很多更高深效率更高的解决方案。。。这里的只是最简单的一种。

#include <iostream>
#include <cstdio>
#include <string.h>
using namespace std;

int f[20],n,sum=0;
int b[30][30];

void biaoji(int dep,int h,int x)
{
    b[dep][h]+=x;
    for (int i=dep+1;i<=n;i++)
    {
        b[i][h]+=x;
        if (h-(i-dep)>0)
            b[i][h-(i-dep)]+=x;
        b[i][h+(i-dep)]+=x;
    }
}

bool check(int dep,int x)
{
    for (int i=1;i<dep;i++)
        if (f[i]==x || f[i]+(dep-i)==x || f[i]-(dep-i)==x)
            return false;
    return true;
}

void checker(int dep)
{
    if (dep==n+1)
    {
        sum++;
        if (sum<=3) 
        {
            for (int i=1;i<n;i++)
                cout<<f[i]<<" ";
            cout<<f[n]<<endl;
        }
        return;
    }
    for (int i=1;i<=n;i++)
    if (!b[dep][i])
    {
        f[dep]=i;
        biaoji(dep,i,1);     //标记
        checker(dep+1);
        biaoji(dep,i,-1);     //复位
    }
}

int main()
{
    freopen("checker.in","r",stdin);
    freopen("checker.out","w",stdout);
    cin>>n;
    memset(b,0,sizeof(b));
    checker(1);
    cout<<sum<<endl;
    return 0;
}