AcWing 1432. 棋盘挑战(Java DFS)
原题链接
中等
作者:
Limited
,
2021-02-06 17:50:25
,
所有人可见
,
阅读 227
思路
- 按行深搜,每行枚举所有列,判断列和对角线是否有冲突情况
- 注意回溯时要还原现场
- 要求输出可用方案序列,需要一个数组存当前选择的列号
- 主辅对角线可通过数组标识开发状态,要确定好行列号和其对角线的数值对应关系
- 结合行列号给对角线排编号,对应关系不唯一,只要不重不漏
- 如,对于第$x$行$y$列,其主对角线编号为$x+y$,辅对角线编号为$x-y+n$($n$为棋盘长度,加上这个偏移量保证最后编号不为负数,便于数组索引)
代码
import java.lang.*;
import java.util.*;
public class Main {
static Scanner scanner = new Scanner(System.in);
static int N, sum; // N存棋盘宽 sum存方案总数
static boolean[][] f = new boolean[15][15]; // 模拟棋盘
// col标记列使用情况 dg标记主对角线 udg标记辅对角线
static boolean[] col = new boolean[15], dg = new boolean[30], udg = new boolean[30];
// 记录当前深搜的方案序列
static int[] ans = new int[15];
static void dfs(int n) {
// 搜到N+1行时 搜索完成 方案数+1 并输出ans序列内容
if (n > N) {
sum++;
if (sum <= 3) {
for (int i = 1; i <= N; i++) {
System.out.print(ans[i] + " ");
}
System.out.println();
}
return;
}
// 遍历本行所有列
for (int i = 1; i <= N; i++) {
if (!col[i] && !dg[n + i] && !udg[i - n + N]) { // 列、对角线均满足要求
col[i] = dg[n + i] = udg[i - n + N] = f[n][i] = true; // 已开发标记
ans[n] = i; // 当前列存入ans序列
dfs(n + 1); // 深搜下一层
col[i] = dg[n + i] = udg[i - n + N] = f[n][i] = false; // 还原现场
ans[n] = 0; // ans也可以不还原 下一个方案会覆盖
}
}
}
public static void main(String[] args) {
N = scanner.nextInt();
dfs(1); // 从第一层开始搜
System.out.println(sum);
}
}