【LeetCode热题100】【回溯】N皇后

题目链接：51. N 皇后 - 力扣（LeetCode）

经典问题，N个皇后，N×N棋盘，直线上不能有多个皇后，找摆法

我们一层一层来摆，这样后面的层因为没有摆，所以判断冲突的时候不需要考虑后面的层，并且这层摆了一个就摆下一层，所以水平方向不需要判断冲突

因此需要写一个判断冲突的函数，判断当前位置往上，往左上，往右上有没有冲突

深度遍历回溯查找可行方案

代码语言：javascript复制

class Solution {
public:
    vector<vector<string> > ans;
    vector<string> an;
    int n;

    bool isValid(int i, int j) {
        for (int k = 0; k < i;   k) // 竖直方向
            if (an[k][j] == 'Q')
                return false;
        for (int x = i, y = j; x >= 0 && y >= 0; --x, --y) // 左斜向上
            if (an[x][y] == 'Q')
                return false;
        for (int x = i, y = j; x >= 0 && y < n; --x,   y) // 右斜向上
            if (an[x][y] == 'Q')
                return false;
        return true;
    }

    void dfs(int level) {
        if (level == n) {
            ans.push_back(an);
            return;
        }
        for (int i = 0; i < n;   i) {
            if (isValid(level, i)) {
                an[level][i] = 'Q';
                dfs(level   1);
                an[level][i] = '.';
            }
        }
    }

    vector<vector<string> > solveNQueens(int n) {
        this->n = n;
        an.assign(n, string(n, '.'));
        dfs(0);
        return ans;
    }
};

return 遍历 函数 int leetcode

0 人点赞