【每日算法】LeetCode 51 —— N 皇后 (一百四十三)

题目内容

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。

给你一个整数 n ,返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案,该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。

示例

示例 1:

输入:n = 4
输出:[[“.Q..”,”…Q”,”Q…”,”..Q.”],[“..Q.”,”Q…”,”…Q”,”.Q..”]]
解释:如上图所示,4 皇后问题存在两个不同的解法。

示例 2:

输入:n = 1
输出:[[“Q”]]

提示

1、1 <= n <= 9
2、皇后彼此不能相互攻击,也就是说:任何两个皇后都不能处于同一条横行、纵行或斜线上。

题解

本题是n皇后问题,主要思路还是深度优先搜索。

这里,我们定义一些布尔数组来存放当前格子是否存在皇后,用于n皇后的规则判断,定义 vectorrow, col, dg,udg用来记录每一行、每一列、每条对角线和反对角线上是否有皇后存在。

使用dfs搜索时需要使用4个参数来记录状态,分别是:当前遍历格子横坐标、当前格子纵坐标、整体已摆放的皇后个数、棋盘大小。
对于每步搜索,有两种选择:

1、当前格子不放皇后,则转移到 dfs(x, y + 1, s, n);
2、如果 (x,y) 所在的行、列、对角线不存在皇后,则当前格子可以摆放皇后,更新row, col, dg,udg后转移到 dfs(x, y + 1, s + 1, n),回溯时不要忘记恢复row, col, dg, udg等状态。

时间复杂度分析:由于 n 个皇后不能在同行同列,所以每行恰有一个皇后,在不考虑对角线的情况下,方案数的上限:第一行有 n 个位置可选,第二行有 n−1 个位置可选,依次类推,可得方案数最多是 n!。所以时间复杂度是 O(n!)。

代码

class Solution {
public:
int n;
vector<bool> col,dg,udg;//用于存储列、对角线、反向对角线
vector<vector<string>> ans;//用于存储答案
vector<string> path;//表示当前搜索的路径

vector<vector<string>> solveNQueens(int _n) {
/*
整体思想就是n皇后的思想,即行、列、对角线不得有重复皇后。
可以定义数组,对列的状态进行存储。对弈对角线,可以通过建立坐标轴映射的方式,把每个点映射到两条对角线上。可以用截距k来表示下标。
*/
n = _n;//使用伪全局变量
col = vector<bool>(n);//当前全部初始化为false
dg = udg = vector<bool>(n * 2);//当前全部初始化为false
path = vector<string>(n,string(n,'.'));//初始化当前最开始的棋盘

dfs(0);
return ans;
}

void dfs(int u){
if(u == n){
//当搜完了之后,记录答案并返回
ans.push_back(path);
return;
}
for(int i = 0; i < n; i++){
//枚举第u行的位置
if(!col[i] && !dg[u - i + n] && !udg[u + i]){
//如果当前第i行没有被搜索过,且两条映射的对角线均没有皇后存在
col[i] = dg[u - i + n] = udg[u + i] = true;
path[u][i] = 'Q';//记录一下方案,即第u行第i个位置
dfs(u + 1);
path[u][i] = '.';//恢复现场
col[i] = dg[u - i + n] = udg[u + i] = false;
}
}
}
};
Author: Frederic Niu
Link: https://www.fredericniu.cn/2021/05/18/【每日算法】LeetCode-51-——-N-皇后-(一百四十三)/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.
我的公众号