有一个NxN的棋盘,将N个棋子放置在棋盘上,使得每行、每列有且只有一个棋子,每条对角线(包括两条主对角线的所有平行线)上至多有一个棋子。 假设N的取值为6,其中一个有效的布局如下。
上面的布局可以用序列2 4 6 1 3 5
来描述,第i个数字表示在第i行相应的列有一个棋子,如下:
行号 1 2 3 4 5 6
列号 2 4 6 1 3 5
请编写程序找出所有满足条件的布局。并将它们以上面的方式输出。输出的序列按字典序排列。
只输出前3个满足条件的布局。最后一行为满足条件的布局总数。
一个整数N (6<=N<=13) 表示棋盘是N x N的。
前3行为前3个解,每个解的两个数字之间用一个空格隔开。第4行为一个整数,表示解的总数。
6
2 4 6 1 3 5 3 6 2 5 1 4 4 1 5 2 6 3 4
这道题也是十分经典的一道dfs的题目了吧。
大致思路很简单:就是遍历每一个点,能放就放,它所站的这行这列对角线标记住。
但是 问题来了 :找到放的点,该怎么标记它所占用的格子呢?
横行竖列很好标记,用一个数组来标记此行,占用为1.
那对角线怎么标记呢???
这里就要用到一个很重要的性质了————————对角线的性质(因为时间不够篇幅有限,就不做十分详细的介绍)
我们可以观察出 从右往左斜的线,各个点之间坐标之间有些关系:
e . g . 6 —— 1 ---> 6 + 1 = 7
5 —— 2 ---> 5 + 2 = 7
4 —— 3 ---> 4 + 3 = 7
这几个点都处于同一条对角线(见题目描述图),而他们的x+y坐标都是相同的,所以这就是副对角线的性质了,标记的时候就只用用当前点的x坐标加上枚举出来的i相加标记为1即可标记完整条对角线。
接下来,从左往右斜的线就是主对角线了,笔者就不进行过多叙述,方法和上面一样,举出例子,总结规律即可。
(怎么还是情不自禁花了这么长篇幅。不行!下次还要水一些)
几个难点和关键点都讲完了,接下来就直接放出代码了:
#include <bits/stdc++.h> using namespace std; int n; int line [105],zhu[105],fu[105], s [105]; int ans = 0; void print () { if(ans < 3){//题目限制只输出前三个(笔者ans++写在后面的,所以为<3) for (int i = 1; i <= n; i ++) { printf ("%d ", s [i]); } printf("\n");//打印输出 } ans++;//输出只输出前三个,但总数还是要加的 } void dfs(int x){//当前枚举到第x个棋子了 if(x == n+1){//如果n个棋子枚举完了就输出; print (); } else{ for (int i=1;i<=n;i++){//枚举每个点 if(line[i] == 0 && zhu[x-i+n] == 0 && fu[x+i] == 0){ //如果主副对角线和行列都没标记过那么就放下棋子 line[i] = 1;//标记行列 zhu[x-i+n] = 1;//标记主对角线 fu[x+i] = 1;//标记副对角线 s [x] = i;//加入输出数组 dfs(x+1);//枚举下一个棋子 line[i] = 0; zhu[x-i+n] = 0; fu[x+i] = 0;//取消标记 } } } } int main() { scanf("%d",&n);//输入 dfs(1);//开始dfs第几个棋子 printf("%d",ans);//输出答案 return 0; }