LeetCode 51. N皇后 / 52. N皇后 II（回溯）
LeetCode 51. N皇后 / 52. N皇后 II（回溯）
Michael阿明
发布于 2020-07-13 17:05:12
发布于 2020-07-13 17:05:12
文章被收录于专栏：Michael阿明学习之路
1. 题目
n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
在这里插入图片描述
上图为 8 皇后问题的一种解法。
给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。
每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。
示例:
输入: 4
输出: [
[".Q..", // 解法 1
"...Q",
"Q...",
"..Q."],
["..Q.", // 解法 2
"Q...",
"...Q",
".Q.."]
]
解释: 4 皇后问题存在两个不同的解法。- LeetCode 52题，类似要求的是方案数，不用枚举出来。
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/n-queens 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
2. 解题
class Solution {
vector<vector<string>> ans;
int N;
public:
vector<vector<string>> solveNQueens(int n) {
vector<string> map(n,string(n,'.'));
N = n;
dfs(map,0);
return ans;
}
void dfs(vector<string>& map, int x)
{
if(x == N)
{
ans.push_back(map);
return;
}
for(int i = 0; i < N; ++i)
{
if(isok(map,x,i))
{
map[x][i]='Q';
dfs(map,x+1);
map[x][i]='.';
}
}
}
bool isok(vector<string>& map, int i, int j)
{
int delta = 1;
while(i-1 >= 0)
{
if(map[i-1][j]=='Q')//竖直方向
return false;
if(j-delta>=0 && map[i-1][j-delta]=='Q')
return false;//左45度
if(j+delta<N && map[i-1][j+delta]=='Q')
return false;//右45度
i--;//向上查找
delta++;//45度增量
}
return true;
}
};
在这里插入图片描述
class Solution {
int sum = 0;
public:
int totalNQueens(int n) {
vector<string> map(n,string(n,'.'));
for(int i = 0; i < n; ++i)
{
map[0][i]='Q';
dfs(map,0,i,n);
map[0][i]='.';
}
return sum;
}
bool isok(vector<string>& map, int x, int y, int &n)
{
int i = 1, j = y;
while(x >= 1)//向上遍历，看冲突不
{
if(map[x-1][j]=='Q')//竖直方向
return false;
if(j-i>=0 && map[x-1][j-i]=='Q')//左45度
return false;
if(j+i<n && map[x-1][j+i]=='Q')//右45度
return false;
i++;//45度张角
x--;//往上找
}
return true;
}
void dfs(vector<string>& map, int x, int y, int& n)
{
if(x==n-1)
sum++;
for(int i = 0; i < n; ++i)
{ //x+1下一行
if(x+1 < n && isok(map,x+1,i,n))
{
map[x+1][i] = 'Q';
dfs(map, x+1, i, n);
map[x+1][i] = '.';
}
}
}
};
在这里插入图片描述
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2020/03/17 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
