AcWing 843. n-皇后问题
原题链接
中等
作者:
小呆呆
,
2019-11-13 23:10:02
,
所有人可见
,
阅读 4766
算法分析
(DFS)
- 按行继续比遍历,其中
col[x]
,dg[y - x + n]
,udg[x + y]
分别记录的是该位置的列,斜,反斜线上是否已经存在过,若均不存在,填入皇后,并递归到下一行
时间复杂度 $O(n^2*n!)$
Java 代码
import java.util.Scanner;
public class Main{
static int N = 20;
static char[][] g = new char[N][N];
static boolean[] col = new boolean[N];
static boolean[] dg = new boolean[N];//正斜
static boolean[] udg = new boolean[N];//反斜
//按行递归
static void dfs(int y,int n)
{
if(y == n)
{
for (int i = 0; i < n; i ++ )
{
for (int j = 0; j < n; j ++ )
System.out.print(g[i][j]);
System.out.println();
}
System.out.println();
return;
}
for(int x = 0;x < n;x++)
{
if(!col[x] && !dg[y - x + n] && !udg[x + y])
{
g[y][x] = 'Q';
col[x] = true;
dg[y - x + n] = true;
udg[x + y] = true;
dfs(y + 1,n);
col[x] = false;
dg[y - x + n] = false;
udg[x + y] = false;
g[y][x] = '.';
}
}
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
for (int i = 0; i < n; i ++ )
for (int j = 0; j < n; j ++ )
g[i][j] = '.';
dfs(0,n);
}
}
高质量题解++
向秦大佬学习!
共同学习进步!
进步!
如果下标从1开始的话,有什么问题吗?我试了试,没有输出结果
···
#include [HTML_REMOVED]
using namespace std;
const int N = 10;
int n;
char g[N][N];
bool st[N],dg[N],udg[N];
void dfs(int u)
{
if(u == n + 1){
for(int i = 1 ; i <= n ; i ++) puts(g[i]);
puts(“”);
return ;
}
}
int main()
{
scanf(“%d”,&n);
}
···
有懂得大佬指教一下
输出问题,一个一个输出就行了
嗯嗯好的我试试,谢谢大佬!
C$\color{red} {这个图蒸滴} $
我看题目范围 n是9呀,我就 const int N=10,结果没过呢,为啥要把N变成20呢,是题目n范围给错了吗?😂😂😂
x + y 是能到 2n 左右的
嗷嗷嗷,懂了。thanks : )
这个题解质量高!!
怎么是O(n*n!)
这里修正一下,我的代码的复杂度是$O(n^2n!)$,如果不算两条对角线的剪枝,从第
0
行枚举到第n-1
行,第0
行所能选的方案是n
,第1
行所能选的方案是n - 1
.....由于,当前行选定了一个位置,那该位置的列项就不能选,则下一行的所能选的方案就比上一行少1
,因此枚举到所有的情况是n!
,由于我的代码输出的复杂度是$O(n^2)$,因此复杂度是$O(n^2n!)$,再加上两条斜对角线也能进行可行性剪枝,运行的次数会更少,因此,再加上两条斜对角线也能进行可行性剪枝,运行的次数会更少,因此$O(n^2*n!)$是一个上限