题目描述

DFS
难点：
① 点下标信息表示：
下标转换为截距 (正对角线y-x由于有些小于0 ∈(-n,n) 所以都加上n)
② 这个思路和 dfs 基本一致，都是递归(下一层)回溯来实现一条路走到底的深搜。只是判断时变成了三个①列；②对角线；③反对角线。

class Solution {
public:
    int n;
    vector<bool> col, diag, udiag; //记录列上，对角线，反对角线上是否有数
    vector<vector<string>> ans;
    vector<string> path; // 当前搜索的方案

    void dfs(int u)
    {
        if (u == n) //如果搜到了最后一步
        {
            ans.push_back(path); //找到了答案，加入ans
            return;
        }
        // y = x + k; 截距k = y - x + n (由于可能小于0所以加n变为正)) 
        // y = -x + k; k = y + x;
        for (int i = 0; i < n; i++)
        {
            if (!col[i] && !diag[u - i + n] && !udiag[u + i])
            {
                col[i] = diag[u - i + n] = udiag[u + i] = true;
                path[u][i] = 'Q';
                dfs(u + 1);
                path[u][i] = '.'; //恢复现场【回溯】
                col[i] = diag[u - i + n] = udiag[u + i] = false;
            }
        }
    }

    vector<vector<string>> solveNQueens(int _n) {
        // 检查三个方向即可。col[]竖着， diag[]对角线，udiag[] 反对角。（当前那些列有Q, 哪些对角线有Q, 哪些反对角有Q)
        // （2n-1）条对角线
        n = _n;
        col = vector<bool>(n); //初始化大小为n
        diag = udiag = vector<bool>(n * 2); // 对角线2n(2n-1就够)
        path = vector<string>(n, string(n, '.')); // 初始化为n个点.
        dfs(0);
        return ans;
    }
};