前导
n皇后是很经典的一道dfs题,只不过这道题输出格式很新颖,需要想一下怎么输出合适
温馨提示:dfs是在算法基础课里讲的,第三章的第一个知识点
扩展题:
AcWing 842. 排列数字
AcWing 843. n-皇后问题
三个问题
- dfs原理
- 递归是怎么实现的
- 正反对角线
解答
1:dfs
基本概念:用大白话来说就是 先是一条路走到黑,然后走不通了再往回回溯
实现方式:递归
时间复杂度:O(n!)
模板:
static int[] path; //用于保存路径
static int[] st; //用于表示该步已经走过,true表示走过了,false表示还没有
static int u,n; //u表示当前是第几步,n表示一共要走几步
void dfs(int u)
{
if(u == n)
{
输出结果;
}
for (int i = 0; i < n; i ++)
{
if (!st[i])
{
path[u] = i; //存值
st[i] = true; //走过
dfs(u + 1); //递归
st[i] = false; //回溯
}
}
2:递归实现
这里建议拿着数据去试一下,就会清楚很多
1:如果还没有找到解决方案,即u != n,就会从头开始判断这个位置有没有危险
2:如果第一个位置有危险,if(!st[0]) = true,就会结束if(!st[0]),然后判断第二个位置是否有危险
3:如果第二个位置没有危险,if(!st[1]) = false,说明我们可以把皇后放在这里,然后去找下一行的皇后
4:等找到了所有的皇后,u == n,我们就可以输出结果了
5:输出第一个结果后,接着就会回溯,把走过的位置设为false,继续找下一个结果
3:正反对角线
我们用dg[]记录正对角线,udg[]来记录反对角线
正对角线的公式是y = x,x - y = 0,因为x>0,y>0,x-y可能会出现负数,而数组中的下标不能为负,所以我们加上了一个偏移量n,就永远不会为负数,=>x-y+n
反对角线也是一样的,y = -x,x + y = 0,就是x + y
java代码
import java.util.Scanner;
public class Main{
static int N = 15;
static int[][] g = new int[N][N]; //储存棋盘
static boolean[] col = new boolean[N]; //列
static boolean[] dg = new boolean[2 * N]; //正对角线
static boolean[] udg = new boolean[2 * N]; //反对角线
static int u,n,cnt; //u表示当前是第几步,n表示一共要走多少步,cnt用于输出前三个
public static void main(String[] args){
Scanner in = new Scanner(System.in);
n = in.nextInt();
for(int i = 0; i < n; i ++) //初始化
{
for(int j = 0; j < n; j ++)
{
g[i][j] = 1;
}
}
dfs(0);
System.out.print(cnt); //输出可行放置方案的总数
}
private static void dfs(int u )
{
if(u == n) //说明找到了一个可行的方案
{
cnt++;
for(int i = 0; i < n; i ++)
{
for(int j = 0; j < n; j ++)
{
if(g[i][j] == 0 && cnt <= 3) System.out.print(j + 1 + " "); //输出结果
}
}
if(cnt <= 3) System.out.println(); //注意只有前三个结果是有空格的
}
for(int i = 0; i < n; i ++)
{
if(!col[i] && !dg[n - u + i] && !udg[u + i])//列,正,反对角线都没有走过,说明在某行找到了皇后
{
g[u][i] = 0;
col[i] = dg[n - u + i] = udg[u + i] = true;
dfs(u + 1); //递归
col[i] = dg[n - u + i] = udg[u + i] = false; //恢复现场
g[u][i] = 1;
}
}
}
}
dg[u + i] udg[n - u + i] 主副对角线规律得说清楚点
已更正,感谢指出