题目描述
检查一个如下的6 x 6的跳棋棋盘，有六个棋子被放置在棋盘上，使得每行、每列有且只有一个，每条对角线(包括两条主对角线的所有平行线)上至多有一个棋子。
上面的布局可以用序列2 4 6 1 3 5来描述，第i个数字表示在第i行的相应位置有一个棋子，如下：
行号 1 2 3 4 5 6
列号 2 4 6 1 3 5
这只是跳棋放置的一个解。请编一个程序找出所有跳棋放置的解。并把它们以上面的序列方法输出。解按字典顺序排列。请输出前3个解。最后一行是解的总个数。
题目链接：https://www.luogu.org/problemnew/show/P1219
方法一：
DFS + 对角线的优化
利用一次函数y=kx+b,因为b为常数，利用b来代表一整条对角线。
对角线优化的说明
AC代码如下：
(代码有具体的解释)
//【DFS】
//【对角线的处理】
//用时: 560ms / 内存: 820KB
#include<iostream>
#include<cstdio>
using namespace std;
int n;
int r[400]; //存储第i的皇后的列的位置
int c[400]; // column[j]
int z1[400]; //左上到右下的对角线 (ld)
int z2[400]; //左下到右上的对角线 (rd)
int total=0;
void print()
{
if(total<=2) //total=0,1,2[三个解]
{
for(int i=1;i<=n;i++)
{
printf("%d ",r[i]); //输出结果
}
printf("\n");
}
total++; //解+1
}
void dfs(int row) //DFS[核心代码]
{
if(row>n) //找到解
{
print();
return;
}
for(int j=1;j<=n;j++)
{
if(c[j]==0 && z1[j+row]==0 && z2[j-row+n]==0) //同列、同对角线无皇后
{
r[row]=j; //在该列放置第row
c[j]=1; //该列置1
z1[j+row]=1; // ld对角线置1
z2[j-row+n]=1; //rd对角线置1
dfs(row+1); //深度向下搜索【递归】
// 恢复原来的状态【回溯】
c[j]=0;
z1[j+row]=0;
z2[j-row+n]=0;
}
}
}
int main()
{
scanf("%d",&n);
dfs(1); //从第一位皇后开始
printf("%d",total);
return 0;
}
方法二：
利用位运算进行优化
（弱弱的我对于位运算也不是特别熟悉）
//【位运算优化】
//用时: 112ms / 内存: 804KB
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n;
int upperlim,row,ld,rd;
int res[25]; //存储一个解的结果
//int all[4][25]; //存储结果【所有】
int ans=0; //可能的解
int sum=0;
void dfs(int row,int ld,int rd)
{
int pos,p;
if(row!=upperlim) //未找到解
{
pos=upperlim&(~(row|ld|rd)); //获取可以放置皇后的所有位置(row|ld|rd获取所有的禁止位置，再取反即可得到可以放置的位置)
while(pos) //pos!=00000000【n个0】
{
p=pos&(-pos); //取出最右边的1【一个可能的位置】
pos=pos-p; //将pos最右边为1的bit清零,也就是为获取下一次的最右可用列使用做准备，
//程序将来会回溯到这个位置继续试探
int num=p;
res[sum++]=__builtin_ffs(num); // 【从右往左数获取皇后所在的列数。因为棋盘对称，所以从左往右数于从右往左数结果一致】
//int __builtin_ffs(unsigned int x)
//返回二进制表示中x的最后一位1（最右边的）是从后向前第几位，比如 7368(1110011001000)返回 4
dfs(row|p,(ld|p)<<1,(rd|p)>>1); //
res[--sum]=0; //回溯【***重要***】
}
}
else //找到一个解
{
ans++; //解+1
if(ans<=3)
{
for(int i=0;i<n;i++) //n个皇后
{
printf("%d ",res[i]);
}
printf("\n");
}
}
}
int main()
{
scanf("%d",&n);
upperlim=(1<<n)-1; //生成n个1组成的二进制数，每一个二进制位(后者说是1)都代表一位皇后
dfs(0,0,0); //从0,0,0开始搜索
printf("%d",ans);
return 0;
}
C++高效位运算：
int __builtin_ffs(unsigned int x)
返回二进制表示中x的最后一位1（最右边的）是从后向前第几位，比如 7368(1110011001000)返回 4
int num=p;
res[sum++]=__builtin_ffs(num);
等价于
int num=p;
int count=0;
while(num)
{
num=num>>1; //右移一位【等同于除2】
count++; //加1
}
res[sum++]=count;
参考资料：
位运算优化：
https://blog.csdn.net/kai_wei_zhang/article/details/8033194
https://blog.csdn.net/Dora_Bin/article/details/52733832?utm_source=blogxgwz5
C++高效位运算：
https://www.cnblogs.com/P6174/p/8759249.html
写在最后:
打一波广告，自己的公众号，不是技术文，主要是分享自己的一些想法，欢迎前来关注，非喜勿喷。
我锨说
网友评论