移动做绩效的网站,企业网站哪家做的好,厦门黄页,建站之星多少钱文档讲解#xff1a;回溯算法总结篇 重新安排行程 N皇后 解数独 51.N皇后
题目链接#xff1a;https://leetcode.cn/problems/permutations/description/
思路#xff1a; 本题的基本含义就是有个N*N的棋盘#xff0c;需要我们放N个皇后在上面#xff0c;满足不能有任… 文档讲解回溯算法总结篇 重新安排行程 N皇后 解数独 51.N皇后
题目链接https://leetcode.cn/problems/permutations/description/
思路 本题的基本含义就是有个N*N的棋盘需要我们放N个皇后在上面满足不能有任意两个皇后位于同一行或者同一列或者同一对角线。 这题我们可以按行搜索每行放一个这样保证了行不重复递归边界条件为放到第N1行这证明前N行找出来了一种答案。下面考虑列和对角线如何不重复 1.针对列我们开设一个全局bool数组标记哪列已经放上了。在搜索每行枚举每个点时判断该列是否有皇后即可有就跳过没有放上皇后搜下一行。 2.针对正对角线我们知道位于同一正对角线上的点有一个性质横纵坐标之和相等因此我们针对坐标和开一个全局bool数组标记放过皇后的点的坐标和即可逻辑类似1。 3.针对斜对角线有类似2的性质横纵坐标之差相等。也针对这个差开个标记数组即可。 有上面三个标记数组按行搜索就行了。
核心代码
class Solution {
private:bool flag[10],book1[20],book2[20];int maxline;vectorstring path;vectorvectorstring ans;void dfs(int x){if(xmaxline){ans.push_back(path);return;}for(int i0;imaxline;i){if(flag[i]||book1[xi]||book2[i-xmaxline]) continue;string s;for(int j0;ji;j) s.;sQ;for(int ji1;jmaxline;j) s.;path.push_back(s);flag[i]true;book1[xi]true;book2[i-xmaxline]true;dfs(x1);flag[i]false;book1[xi]false;book2[i-xmaxline]false;path.pop_back();}return;}
public:vectorvectorstring solveNQueens(int n) {maxlinen;memset(flag,false,sizeof(flag));memset(book1,false,sizeof(book1));memset(book2,false,sizeof(book2));dfs(0);return ans;}
};
今日总结 今日学习时长3h题目很难我只会做N皇后还是因为以前做过所以很快就写出来了。第一道基本想出了思路但是映射关系定义的不好就没写出来没想到map套map。第三题想了很久但没啥好思路今天没时间总结其他两道了放在周末吧。
