题解 | N皇后问题

#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 the n
     * @return int整型
     */
    int bound;
    vector<bool> col, dg, udg;
    vector<string> path;
    vector<vector<string>> ans; 

    int Nqueen(int n) {
        bound = n;
        col = vector<bool> (n);
        dg = udg = vector<bool> (n * 2);
        path = vector<string> (n, string(n, '.'));
        dfs(0);
        return ans.size();
    }

    void dfs(int u) {
        if (u == bound) {
            ans.push_back(path);
            return;
        }
        for (int i = 0; i < bound; i++) {
            if (!col[i] && !dg[u - i + bound] && !udg[u + i]) {
                col[i] = dg[u - i + bound] = udg[u + i] = true;
                path[u][i] = 'Q';
                dfs(u + 1);
                path[u][i] = '.';
                col[i] = dg[u - i + bound] = udg[u + i] = false;
            } 
        }
    }
};