题目描述

这么简单不想跟没有AC的人讲话
blablabla

样例

#include <iostream>

using namespace std;

typedef long long LL;
char a[15][15];

bool check(int i, int j, int n) {
    for (int tt = 1; tt <= n; tt ++ ) {
        if (a[i][tt] == 'Q') {
            return false;
        }
    }

    for (int tt = 1; tt <= n; tt ++ ) {
        if (a[tt][j] == 'Q') {
            return false;
        }
    }

    for (int tt = 1; tt <= n; tt ++ ) {
        if (i+j-tt >= 1 && i+j-tt <= n && a[tt][i+j-tt] == 'Q') {
            return false;
        }
    }

    for (int tt = 1; tt <= n; tt ++ ) {
        if (tt-i+j >= 1 && tt-i+j <= n && a[tt][tt-i+j] == 'Q') {
            return false;
        }
    }

    return true;
}

void print(int n) {
    for (int i = n; i >= 1; i -- ){
        for (int j = 1; j <= n; j ++ ) {
            cout << a[i][j];
        }
        cout << endl;
    }
    cout << endl;
}

void dfs(int i, int n) {
    //cout << i << endl;
    for (int j = 1; j <= n; j ++ ) {
        if (check(i, j, n)) {
            if (i == n) {
                a[i][j] = 'Q';
                print(n);
                a[i][j] = '.';
            }else{
                a[i][j] = 'Q';
                dfs(i + 1, n);
                a[i][j] = '.';
            }
        }
    }
}

int main() {
    LL n;
    cin >> n;

    for (int i = 1; i <= n; i ++ ) {
        for (int j = 1; j <= n; j ++ ) {
            a[i][j] = '.';
        }
    }
    dfs(1, n);

}

算法1

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

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

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

blablabla

时间复杂度

参考文献

C++ 代码

blablabla