题解：UVA11195 Another n-Queen Problem

· · 题解

UVA11195 Another n-Queen Problem 题解

Links:
题目传送门（洛谷）
题目传送门（Uva）
这是本蒟蒻 2026 年的第一篇题解。

题目大意

这题和八皇后模板原题 P1219 的唯一区别就是，有亿一些格子不能放皇后，且这些坏格子不阻挡皇后间的攻击。

思路

我们可以深搜解决本题。深搜的终止条件是行号 >n。
首先，我们开一个 bad 数组记录坏格子。
假设第 a 行的皇后放在第 col_a 列，那对于第 i 行，怎么判断当前放的是否合法呢？首先这个格子不是坏格子。如果不是坏格子，判断方案如下：我们先把假设的第 i 行方案放好，然后对于第 1\sim i-1 行（特别地，i=1 时非坏格子一定合法）进行枚举，假设当前枚举的是第 c 行，则若 col_c=col_i 或 col_c-col_i=\left|c-i\right|，则当前方案是不合法的。

一部分代码

:::success[变量定义代码]

int n, col[20], cnt = 0;
bool bad[20][20];

::: :::success[不是坏格子的方案第 i 行合法性判断代码]

bool check(int i) {
    for (int j = 1; j < i; j++) {
        if (col[j] == col[i] || col[j] - col[i] == j - i || col[j] - col[i] == i - j) {
            return false;
        }
    }
    return true;
}

::: :::success[深搜代码]

void dfs(int k) {
    if (k > n) {
        cnt++;
        return;
    }
    for (int i = 1; i <= n; i++) {
        col[k] = i;
        if (!bad[k][i] && check(k)) {
            dfs(k + 1);
        }
    }
}

:::