题目链接：51. N 皇后

题解：

经典的N皇后问题！

题目简述：

n * n 的棋盘放n个皇后，保证每行每列每条斜线都不能有大于一个皇后！

题解：

DFS来一遍即可！

使用col dg udg分别存储列和两条对角线是否有皇后。使用res存储答案，使用path存储路径。

void dfs(int i, int n)

  • i：代表第几层
  • n：代表皇后数或棋盘行列数

递归出口： i == n即n个皇后都已经找到，将当前方案加入答案res

使用dg[i + j]和udg[i - j + n] 来标识两条对角线，原因就是你可以将它看成坐标系，一条对角线为y = x + b，另一条为y = -x + b，即可解的b = y - x, b = y + x，y - x可能越界，让他偏移n，即可保证不越界。

递归开始： 只要列以及两条斜线以及没有被访问过，即可访问！使用path[i][j]记录路径，表示i行的j列有一个皇后，更新标记，最后清空标记！

注意：数组的初始化，path需要全部初始化为.，col要初始化n个位置，dg udg要初始化n * 2个位置。

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    vector<bool> col, dg, udg;
    vector<vector<string>> res;
    vector<string> path;
    vector<vector<string>> solveNQueens(int n) {
        col = vector<bool>(n);
        dg = udg = vector<bool>(n * 2);
        path = vector<string>(n, string(n, '.'));
        dfs(0, n);
        return res;
    }
    void dfs(int i, int n){
        if(i == n){
            res.push_back(path);
            return;
        }
        for(int j = 0; j < n; j++){
            if(!col[j] && !dg[i + j] && !udg[i - j + n]){
                col[j] = dg[i + j] = udg[i - j + n] = true;
                path[i][j] = 'Q';
                dfs(i + 1, n);
                path[i][j] = '.';
                col[j] = dg[i + j] = udg[i - j + n] = false;
            }
        }
    }
};