0分求解

Little_Fish_Is_Happy @ 2023-12-19 20:04:49

#include <bits/stdc++.h>
using namespace std;
int cnt,n;
int a[100];
bool h[100];
bool l[100];
bool lx[200];
bool ly[200];
void dfs(int t){
    if(t==n+1){
        cnt++;
        if(cnt<=3){
            for(int i=1;i<=n;i++)
            cout<<a[i]<<" ";
            cout<<endl;
        }
        return ;
    }
    for(int i=1;i<=n;i++) {
        if( !h[t] && !l[i] && !lx[t-i+10] && !ly[t+i] ){
            a[t]=i;
            h[t]=true;
            l[i]=true;
            lx[t-i+10]=true;
            ly[t+i]=true;
            dfs(t+1) ;
            h[t]=false;
            l[i]=false;
            lx[t-i+10]=false;
            ly[t+i]=false;
        }
    }
}
int main(){
    dfs(1);
    cin>>n;
    cout<<cnt;
    return 0;
}

by zuanshijian @ 2023-12-19 20:13:54

八皇后是一个经典的回溯法练习题。可以扩展到n*n的棋盘。

常用的解法是二维数组，但是超级慢。我们可以另辟蹊径：一个棋盘的格子只有两种可能：0或1。现在要满足，每一条横行竖列对角线至多一个1，其它都为0。既然这样，我们为什么不想想整数呢？整数是32个0和1的位组成的，刚好可以表示每一个状态。

基本思路还是这样，从上往下进行，一行只放一颗棋子，然后再检查它对竖列和对角线的影响。只不过，要用位运算表达出来。比如，某一行的状态是00001000（也就是整数8），那么下一行的禁止位置（用x表示）就包括：000x0000（左对角线，整数16），0000x000（竖列，整数8），00000x00（右对角线，整数4）三个。这是基本情况。

另外，影响下一行的不只是上一行，还有上两行，三行...等等等等。那么我们看一下，00001000对下两行的禁止位置，分别是00x00000，0000x000，000000x0这三个。

所以，可以这样设计。如果已知某一行的左对角线禁止位置为l，竖列禁止位置为d，右对角线禁止位置为r，这一行放棋子的状态为s，则有下列位运算表达式：

本行禁止位置（记为forbid）为：forbid = l | d | r

下一行左对角线禁止位置：(l | s) << 1

下一行竖列禁止位置：d | s

下一行右对角线禁止位置：(r | s) >> 1

某个状态s可放棋子：(forbid | s) != forbid

这样，运行速度可以达到常规数组法的4-10倍。如果用数组法TLE的童鞋不妨试试这个方法。

另外，根据实际测试，这个程序能跑动的最大n就是15。所以，用32位整数是足够的。

特别需要注意的是，C语言的右移运算有“算术右移”和“逻辑右移”的区别，前者是高位补符号位，后者是高位补0。我们需要的正是后者，但不同编译器对有符号数右移的解释并不相同。所以为了避免这个bug，表示状态的整数应该为unsigned。

最后贴一下AC代码：

by yujiahaoa @ 2024-01-07 07:57:57

@zuanshijian 最后贴一下AC代码暴露了（doge）