n-queens(n皇后问题)

╰+哭是因爲堅強的太久メ 2022-09-02 04:29 132阅读 0赞

class Solution {
    public:
        /**
         * 
         * @param n int整型 
         * @return int整型
         */
        int totalNQueens(int n) {
            vector<vector<string>> res;
            vector<string> cur(n, string(n, '.')); // 初始化棋盘，所有的位置都没有摆放皇后
            dfs(res, cur, n, 0);
            return res.size();
        }
            void dfs(vector<vector<string>> &res, vector<string> &cur, int &n, int row) {
            if (row == n) { // 当超出行数超出了棋盘，则把这次搜索的结果放入res中。
                res.push_back(cur);
                return;
            }
     
            for (int j = 0; j < n; j++) {
                if (isValid(cur, n, row, j)) { // 判断在(row, j)处是否可以放一个皇后
                    cur[row][j] = 'Q'; // 如果可以，则放一个皇后
                    dfs(res, cur, n, row + 1); // 继续在下一行找一个位置放皇后
                    cur[row][j] = '.'; // 因为需要找到所有可能的情况，所以必然需要对每一行进行回退。去判断这一行的下一列是否可以放皇后。
                }
            }
        }
     
        bool isValid(vector<string> &cur, int &n, int row, int col) {
            // 检查列
            for (int i = 0; i < row; i++) {
                if (cur[i][col] == 'Q') {
                    return false;
                }
            }
            // 检查反斜线
            for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
                if (cur[i][j] == 'Q') {
                    return false;
                }
            }
            // 检查斜线
            for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
                if (cur[i][j] == 'Q') {
                    return false;
                }
            }
            return true;
        }
    };

# n-queens(n皇后问题) #

> **题目链接：**[牛客网][Link 1]  
> **题目描述：**  
> N皇后问题是把N个皇后放在一个N×N棋盘上，使皇后之间不会互相攻击。  
> 给出一个整数n，返回n皇后问题的所有摆放方案  
> 例如：  
> 4皇后问题有两种摆放方案

题目解析：这个问题就是n个皇后摆放在n\*n的棋盘格中，使得横、竖和两个对角线方向均不会同时出现两个皇后。这道题我一直都不会做，于是学习了牛客网黄汉韬的做法。  
首先将所有的位置都置为没有放置皇后。  
用递归的方法从第一行开始，判断该点能否放置皇后，如果可以则说明这一行就只能这么放置了，然后递归进入下一行，当行数为n时则说明超出了棋盘，说明当前摆放符合n皇后问题，则加入摆放规则。同时跳出这一层的递归，因为要找出所有的方法，所以将该位置重新置为没有放置皇后，然后继续跳出递归，遍历该行的下一个位置能否符合。利用这种递归将会遍历完整个棋盘的所有摆放方式。因为对于每一行的每一个点，都会遍历从它往下的任意一种可能性。

[Link 1]: https://www.nowcoder.com/practice/c77ac599d0764433a5946610a7626768?tpId=46&tqId=29128&tPage=1&rp=1&ru=/ta/leetcode&qru=/ta/leetcode/question-ranking