题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla
#include <iostream>
using namespace std;
const int N = 10;
int n;
bool row[N], col[N], dg[2 * N], udg[2 * N];
char g[N][N];
void dfs(int x, int y, int s) {
    if (s > n) return;
    if (y == n) {
        y = 0;
        x++;
    }

    if (x == n) {
        if (s == n) {
            for (int i = 0;i < n;i++) puts(g[i]);
            puts("");
        }
        return;
    }

    dfs(x, y + 1, s);

    if (!row[x] && !col[y] && !dg[y - x] && !udg[y + x + n]) { // 副对角线 y = -x + b ->    b = y + x
        g[x][y] = 'Q';
        row[x] = col[y] = dg[y - x] = udg[y + x + n] = true;
        dfs(x, y + 1, s + 1);
        g[x][y] = '.';
        row[x] = col[y] = dg[y - x] = udg[y + x + n] = false;
    }
}
int main(void) {
    scanf("%d", &n);
    for (int i = 0;i < n;i++)
        for (int j = 0;j < n;j++) g[i][j] = '.';
    dfs(0, 0, 0);
        return 0;
}