【leetcode】51.N皇后

class Solution {
public:
    vector<vector<string>> ans; // 存储的最终结果
    vector<string> path; // 存储当前的一种放置方式
    vector<int> col, dg, undg; // 标志 列、斜对角线、正对角线上是否有Q

    void dfs(int u, int n) {
        if (u == n) { // 当深搜到第n行时，说明前n行（0~n-1）都已经有Q了，保存结果并返回
            ans.push_back(path);
            return;
        }
        for (int i = 0; i < n; i++) {
            if (col[i] == 0 && dg[n - 1 - u + i] == 0 && undg[u + i] == 0) {
                path[u][i] = 'Q';
                col[i] = 1;
                dg[n - 1 - u + i] = 1;
                undg[u + i] = 1;
                dfs(u + 1, n);
                path[u][i] = '.';
                col[i] = 0;
                dg[n - 1 - u + i] = 0;
                undg[u + i] = 0;
            }
        }
    }

    vector<vector<string>> solveNQueens(int n) {
        col.resize(n, 0);
        dg.resize(2 * n - 1, 0);
        undg.resize(2 * n - 1, 0);
        path.resize(n, string(n, '.'));
        int u = 0;
        dfs(u, n); // 开始第 0 行
        return ans;
    }
};