写在前面
我又回来了!
偷了几天懒,还认识我吗?甭管认识不认识,还是要自我介绍一番:本人是初学c++的初中生,还是个蒟蒻,最要命的是没有脑子。今天,还请允许我浪费您一点时间,叨叨上几句。
本题目来自于洛谷,网址https://www.luogu.com.cn/problem/P1219,建议在洛谷上看一下。
本题解非盈利,无恶意,目的明确:分享经验,打发时间,同时,让更多的人被我带偏。因此,题解中可能有的侵权行为还希望您与我联系联系。
毕竟作者是个蒟蒻,一点水平都没有,因此欢迎对错误的批评指正!
题面(复制于洛谷)
[USACO1.5] 八皇后 Checker Challenge
题目描述
一个如下的 \(6 \times 6\) 的跳棋棋盘,有六个棋子被放置在棋盘上,使得每行、每列有且只有一个,每条对角线(包括两条主对角线的所有平行线)上至多有一个棋子。
上面的布局可以用序列 \(2\ 4\ 6\ 1\ 3\ 5\) 来描述,第 \(i\) 个数字表示在第 \(i\) 行的相应位置有一个棋子,如下:
行号 \(1\ 2\ 3\ 4\ 5\ 6\)
列号 \(2\ 4\ 6\ 1\ 3\ 5\)
这只是棋子放置的一个解。请编一个程序找出所有棋子放置的解。
并把它们以上面的序列方法输出,解按字典顺序排列。
请输出前 \(3\) 个解。最后一行是解的总个数。
输入格式
一行一个正整数 \(n\),表示棋盘是 \(n \times n\) 大小的。
输出格式
前三行为前三个解,每个解的两个数字之间用一个空格隔开。第四行只有一个数字,表示解的总数。
样例 #1
样例输入 #1
6
样例输出 #1
2 4 6 1 3 5
3 6 2 5 1 4
4 1 5 2 6 3
4
提示
【数据范围】
对于 \(100\%\) 的数据,\(6 \le n \le 13\)。
题目翻译来自NOCOW。
USACO Training Section 1.5
题目解释
原题中有个不错的例子:
题目是个什么意思呢?
就是说,一个棋子,横着,竖着,斜着,都不会有其他棋子,这就对了。(可以看看上面哦)
那怎么办到?
在这里,我采用大法师DFS。按横行枚举每个棋子,将竖列与对角线标起来,即可。
另外,对角线上的点坐标有规律:左上-右下者,同一线上差相等(i-j);右上-左下者,同一线上和相等(i+j)
代码实现
首先,依然是准备工作
int a[15],b[15],c[30],d[30];//a,b,c,d分别代表横行纵坐标、竖列占用情况、右上-左下对角线占用情况、左上-右下对角线占用情况。
int n,sum;//n意义见题面,sum为方案数记录
DFS输出代码
if(i==n+1)//搜索到棋盘之外,说明完成搜索
{
if(sum<3)//方案数小于3
{
for (int k=1;k<=n;k++)
cout<<a[k]<<" ";//输出方案
cout<<endl;
}
sum++;//方案数自增
}
DFS作业代码
for(int j=1;j<=n;j++)//搜索该横行每一竖列
if(!b[j] && !c[i+j] && !d[i-j+n-1])//该位置上下、对角线均无棋子,即符合要求
{
a[i]=j;//记录纵坐标
b[j]=1;//竖列标记
c[i+j]=1;//对角线之一标记
d[i-j+n-1]=1;//对角线之二标记(+n防止i-j<1造成数组越界)
dfs(i+1);//搜索下一行
b[j]=0;//消除全部标记以供再次使用
c[i+j]=0;
d[i-j+n-1]=0;
}
主函数(不必多解释了吧)
int main()
{
cin>>n;
dfs(1);
cout<<sum<<endl;
return 0;
}
完整代码
#include<iostream>
#include<cstdio>
using namespace std;
int a[15],b[15],c[30],d[30];
int n,sum;
void dfs(int i)
{
if(i==n+1)
{
if(sum<3)
{
for (int k=1;k<=n;k++)
cout<<a[k]<<" ";
cout<<endl;
}
sum++;
}
for(int j=1;j<=n;j++)
if(!b[j] && !c[i+j] && !d[i-j+n-1])
{
a[i]=j;
b[j]=1;
c[i+j]=1;
d[i-j+n-1]=1;
dfs(i+1);
b[j]=0;
c[i+j]=0;
d[i-j+n-1]=0;
}
}
int main()
{
cin>>n;
dfs(1);
cout<<sum<<endl;
return 0;
}
请注意
- 在进行左上-右下的对角线的标记时一定记得+n,否则会造成数组越界哦~
- 完成搜索要回溯,也就是清楚标记
- 对角线:i+j表示右上-左下对角线,而i-j+n-1表示左上-右下对角线!成功把你绕晕了吗?哈哈~
时间复杂度
最大值是13,循环次数为4674890次。数据规模偏小,因此虽然时间复杂度高,但也绝对没问题。
洛谷运行结果如下:
深搜这样我就挺满意了(~ ̄▽ ̄)~
写在最后
回归是不是挺惊喜?没有?我伤心了。
就不再重申开头了。
这次写题解的速度突破了1小时呢!你为我感到自豪,快说!
明天见喽~