www.luogu.com.cn

基本思路

深度优先搜索（DFS）

由于题目数据很小（6≤n≤136 \le n \le 13），我们可以采用打表深度优先搜索的方式完成这道题。
定义四个布尔数组分别表示表格的行，列，两个对角线上是否有旗子存在。
如图所示。

https://z1.ax1x.com/2023/10/02/pPLIhdJ.png

抽象代码如下↓

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
44
45
46
47
48
49
50
#include <bits/stdc++.h>
using namespace std;

const int N = 50;//常量记得开大一点
int n, sum, a[N], b[N], c[N], d[N];
// n:网格大小 sum:方案总数
// a,b,c,d数组分别代表行，列，左下到右上的对角线，左上到右下的对角线

void dfs(int i) // 核心代码
{
    if (i > n) // 判断是否到达边界
    {
        if (sum <= 2) // 输出前三个方案数
        {
            for (int k = 1; k <= n; k++)
                cout << a[k] << ' ';
            cout << endl;
        }
        sum++;	// 仍要加上一个方案数
        return; // 结束
    }

    for (int j = 1; j <= n; j++) // 每列进行遍历
    {
        if ((!b[j]) && (!c[j + i]) && (!d[i - j + n]))
        {
            a[i] = j;
            b[j] = 1;
            c[i + j] = 1;
            d[i - j + n] = 1; // 标记放置后的行、列、对角线上的标记

            dfs(i + 1); // 进行下一次搜索

            b[j] = 0;
            c[i + j] = 0;
            d[i - j + n] = 0; // 搜索完毕后清除标记
            // 也可以写成 memset(b,0,sizeof(b));
        }
    }
}

int main()
{
    cin >> n; // 唯一の输入

    dfs(1); // 开始从头搜索

    cout << sum << endl;
    return 0;
}