第二种解法
算法思路
使用dfs算法在每一行的每一列尝试放置皇后。
使用数组 row、col 和 s 来标记行、列和放置的皇后数量。
如果已经放置了 n 个皇后,输出当前解。
递归调用DFS,尝试在下一列放置皇后。
回溯的过程中,撤销当前位置的皇后。
复杂度分析
时间复杂度:O(n!),其中 n 为输入的正整数。因为对于每个位置,都需要尝试 n 个数字。
空间复杂度:O(n),递归调用深度为 n。
区别
1.递归函数 dfs 接收三个参数 x、y、s,其中 x 表示当前放置皇后的行数,y 表示当前放置皇后的列数,s 表示已经放置的皇后数量。
2.在每一行的每一列尝试放置皇后,但通过递归深度优先搜索的同时,会跳过不放置皇后的情况,而在递归调用之前和之后继续搜索下一列。
3.仍然使用二维数组 g[N][N] 表示棋盘状态,但 ‘Q’ 的放置与否通过数组 row 来判断,而不是通过棋盘数组。
C++ 代码
#include<iostream>
using namespace std;
const int N = 20;
int n;
char g[N][N];
bool col[N], row[N], dg[N], udg[N];
// 深度优先搜索函数
void dfs(int x, int y, int s)
{
// 如果一行结束,移到下一行的第一列
if (y == n)
{
y = 0;
x++;
}
// 如果已经遍历完所有行
if (x == n)
{
// 如果当前方案中放置了 n 个皇后,输出解
if (s == n)
{
for (int i = 0; i < n; i++)
puts(g[i]);
puts("");
}
return;
}
// 不放置皇后,继续搜索下一列
dfs(x, y + 1, s);
// 放置皇后的条件判断
if (!row[x] && !col[y] && !dg[x + y] && !udg[x - y + n])
{
g[x][y] = 'Q';
row[x] = col[y] = dg[x + y] = udg[x - y + n] = true;
// 递归调用DFS,搜索下一行
dfs(x, y + 1, s + 1);
// 回溯,撤销当前位置的皇后
row[x] = col[y] = dg[x + y] = udg[x - y + n] = false;
g[x][y] = '.';
}
}
int main()
{
// 输入棋盘大小
cin >> n;
// 初始化棋盘
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
g[i][j] = '.';
}
}
// 调用DFS函数,从第一行第一列开始放置皇后
dfs(0, 0, 0);
return 0;
}
大佬牛逼