代码随想录算法训练营29期Day30|LeetCode 332,51,37

本文介绍: 重新安排行程、N皇后、解数独

文档讲解：回溯算法总结篇重新安排行程 N皇后解数独

51.N皇后

题目链接：https://leetcode.cn/problems/permutations/description/

思路：

本题的基本含义就是有个N*N的棋盘，需要我们放N个皇后在上面，满足不能有任意两个皇后位于同一行或者同一列或者同一对角线。

这题我们可以按行搜索，每行放一个，这样保证了行不重复，递归边界条件为放到第N+1行，这证明前N行找出来了一种答案。下面考虑列和对角线如何不重复：

1.针对列，我们开设一个全局bool数组，标记哪列已经放上了。在搜索每行枚举每个点时，判断该列是否有皇后即可，有就跳过，没有放上皇后搜下一行。

2.针对正对角线，我们知道位于同一正对角线上的点有一个性质：横纵坐标之和相等，因此我们针对坐标和开一个全局bool数组，标记放过皇后的点的坐标和即可，逻辑类似1。

3.针对斜对角线，有类似2的性质：横纵坐标之差相等。也针对这个差开个标记数组即可。

有上面三个标记数组，按行搜索就行了。

核心代码：

class Solution {
private:
    bool flag[10],book1[20],book2[20];
    int maxline;
    vector<string> path;
    vector<vector<string>> ans;
    void dfs(int x){
        if(x==maxline){
            ans.push_back(path);
            return;
        }
        for(int i=0;i<maxline;i++){
            if(flag[i]||book1[x+i]||book2[i-x+maxline]) continue;
            string s="";
            for(int j=0;j<i;j++) s+=".";
            s+="Q";
            for(int j=i+1;j<maxline;j++) s+=".";
            path.push_back(s);
            flag[i]=true;
            book1[x+i]=true;
            book2[i-x+maxline]=true;
            dfs(x+1);
            flag[i]=false;
            book1[x+i]=false;
            book2[i-x+maxline]=false;
            path.pop_back();
        }
        return;
    }
public:
    vector<vector<string>> solveNQueens(int n) {
        maxline=n;
        memset(flag,false,sizeof(flag));
        memset(book1,false,sizeof(book1));
        memset(book2,false,sizeof(book2));
        dfs(0);
        return ans;
    }
};