LeetCode刷题--- N 皇后

    bool checkCol[10], checkDig1[20], checkDig2[20];
    vector<vector<string>> ret;
    vector<string> path;
    int N;

• ret（存储解决?案的?维字符串数组 ?）
• path（?于存储每个皇后的位置的?维整数数组）
• N（n 的大小）
• checkCol（记录每?列上是否已经有皇后的布尔型数组）
• checkDig1（记录对?线上的主线是否已经有皇后的布尔型数组）
• checkDig2（记录对?线上的副线是否已经有皇后的布尔型数组）

（2）设计递归函数

void dfs(int row);

• 参数：row（表示现在要处理的行数）；
• 返回值：无；
• 函数作用：在当前?放??个不发?冲突的皇后，查找所有可?的?案使得放置 n 个皇后后不发?冲突。

1. 递归结束条件：如果 row 等于 n ，则表?已经找到?组解决?案，此时将每个皇后的位置存储到字符串数组 ret?中，并将 path?存储到 ret?数组中，然后返回；
2. 枚举当前?的每?列，判断该列、两个对?线上是否已经有皇后：
   1. 如果有皇后，则继续枚举下?列；
   2. 否则，在该位置放置皇后，并将 checkCol[10], checkDig1[20], checkDig2[20];对应的位置，设为 true ，表?该列和对?线上已经有皇后：
3. 递归调? dfs 函数，搜索下??的皇后位置。如果该?案递归结束，则在回溯时需要将checkCol[10], checkDig1[20], checkDig2[20]; 对应的位置设为 false ，然后继续枚举下?列；

以上思路讲解完毕，大家可以自己做一下了

代码实现

class Solution {
public:
    bool checkCol[10], checkDig1[20], checkDig2[20];
    vector<vector<string>> ret;
    vector<string> path;
    int N;

    void dfs(int row)
    {
        if (row == N)
        {
            ret.push_back(path);
            return;
        }
        for (int col = 0; col < N; col++) // 尝试在这??放皇后
        {
            // 剪枝
            if (!checkCol[col] && !checkDig1[row - col + N] && !checkDig2[row +col])
            {
                path[row][col] = 'Q';
                checkCol[col] = checkDig1[row - col + N] = checkDig2[row +col] = true;

                dfs(row + 1);

                path[row][col] = '.';                // 恢复现场
                checkCol[col] = checkDig1[row - col + N] = checkDig2[row +col] = false;
            }

        }
    }
    vector<vector<string>> solveNQueens(int n) 
    {
        N = n;
        path.resize(n);
        for (int i = 0; i < n; i++)
        {
            path[i].append(n, '.');
        }

        dfs(0);
        return ret;
    }
};