P1219. 八皇后 Checker Challenge

发表于 分类于 阅读次数： Waline： 本文字数： 328 阅读时长 ≈ 1 分钟

考点

  • DFS

题解

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
#include <bits/stdc++.h>

using namespace std;

const int LEN = 15;

int ans, N, cols[LEN], l_dia[2 * LEN], r_dia[2 * LEN], record[LEN];

void dfs(int row)
{
    if (row > N)
    {
        if (++ans <= 3)
        {
            for (int i = 1; i <= N; ++i)
                cout << record[i] << " ";
            cout << endl;
        }
        return;
    }
    for (int col = 1; col <= N; ++col)
    {
        if (cols[col] || l_dia[row - col + 13] || r_dia[row + col])
            continue;
        cols[col] = l_dia[row - col + 13] = r_dia[row + col] = 1;
        record[row] = col;
        dfs(row + 1);
        cols[col] = l_dia[row - col + 13] = r_dia[row + col] = 0;
    }
}

int main()
{
    cin >> N;
    dfs(1);
    cout << ans;
    return 0;
}

思路

要保证同一行、同一列、左对角线和右对角线只有一个棋子，各用一个一维数组记录对应位置是否有棋子即可

我选择的是按行递归，所以行记录数组就免了（下一轮递归的行号肯定大于当前行号，不会重复）

难点在于左对角线和右对角线的规律，以N = 6为例子：

  • 主左对角线（即{1, 1},{2, 2},{3, 3}所在的对角线)的左侧，左对角线的元素行号 - 列号大于0

    主左对角线上的元素，行号 - 列号等于0

    主左对角线右侧，左对角线的元素行号 - 列号小于0；数组没有负数下标，＋13转正就行

  • 任意一条右对角线上的元素，它们之间行号 + 列号的和都是相等的