DFS 专题 N皇后

DFS 其实会超时的，打表。

# include <cstdio>
# include <cstring>

# define N 10 + 5

int n, ans;
int solu[N];
bool vis[N];

void dfs(int cnt)
{
    if (cnt == n)
    {
        ++ans;
        return ;
    }
    bool ok;
    for (int i = 1; i <= n; ++i) if (vis[i] == false)
    {
        ok = true;
        for (int j = 1; j <= cnt; ++j)
        {
            if ( i+cnt+1 == solu[j]+j ||
                 cnt+1-i == j-solu[j] )     // BUG : i-cnt-1 == j-solu[j]
            {
                ok = false;
                break;
            }
        }
        if (ok)
        {
            vis[i] = true;
            solu[cnt+1] = i, dfs(cnt+1);
            vis[i] = false;
        }
    }
}

void solve(void)
{
    ans = 0;
    memset(vis, false, sizeof(vis));
    dfs(0);
    printf("%d\n", ans);
}

int main()
{
  const int f[] = {0,1,0,0,2,10,4,40,92,352,724};
    while (scanf("%d", &n), n)
        //solve();
        printf("%d\n", f[n]);

    return 0;
}

/**/