题目内容:

image-20210319190026645

题目分析:

一道深搜题,在搜索过程中标记。

题目中说明了棋子的占位规则,同横列内有且只能由一个棋子,每条对角线至多有一个棋子(也可以没有)。

输入只有一个n,代表棋盘的边长,要求输出前三种棋子排列方式以及共有多少种排列方式。

用DFS做,就是搜索每行的棋子应该在哪个位置,搜索到一个之后,就往下搜索下一行的棋子可以在什么位置。在这个搜索过程中标记每个被放下的棋子所占领的位置,即占领了那个棋子所在的行,列,两个方向的对角线,在往下搜索的过程中需要考虑位置是否已经被其他棋子占领,若未占领即可放下,若已占领则判断下一个位置。当搜索变量超过边界(边长n)后,则表示该排列方式已经搜索完成,如果是前三种输出即可,然后回溯。

下面看具体代码理解:

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <iostream>
using namespace std;

int h[15],l[15]={0},lt[30]={0},rt[30]={0},n,sum=0;

int dfs(int a){
if(a<=n){
for(int i=1;i<=n;i++){
if(l[i]==0 && lt[a-i+n]==0 && rt[a+i-1]==0){
h[a]=i;
l[i]=1;
lt[a-i+n]=1;
rt[a+i-1]=1;

dfs(a+1);

l[i]=0;
lt[a-i+n]=0;
rt[a+i-1]=0;
}
}
}else{
sum++;
if(sum<=3){
for(int i=1;i<=n;i++){
if(i!=n)
cout<<h[i]<<" ";
else
cout<<h[i]<<endl;
}
}
return 0;
}

return 0;
}

int main() {
cin>>n;
dfs(1);
cout<<sum<<endl;
return 0;
}