记录一道dfs的题目，
这道题对于刚接触dfs的同学来说算是一道不错的题目了，
能够帮助我们理解得更深刻…
题目：受伤的皇后
题目描述
有一个 n×n 的国际象棋棋盘（n 行 n 列的方格图），请在棋盘中摆放 n 个受伤的国际象棋皇后，要求：
- 任何两个皇后不在同一行。
- 任何两个皇后不在同一列。
- 如果两个皇后在同一条 45 度角的斜线上，这两个皇后之间行号的差值至少为 3 。
请问一共有多少种摆放方案。
输入描述
输入的第一行包含一个整数 nn。
其中，1≤n≤10。
输出描述
输出一个整数，表示答案。
输入输出样例
示例 1
输入
4输出
2运行限制
- 最大运行时间：1s
- 最大运行内存: 128M
import java.io.*;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
static int max;
static int[] array = new int[10];
static int count = 0;//解法数目
public static void main(String[] args) throws IOException {
String readLine = br.readLine();
max = Integer.parseInt(readLine);
dfs(0);
bw.write(String.valueOf(count));
bw.flush();
br.close();
bw.close();
}
private static void dfs(int n) {
if (n == max) {
count++;
return;
}
for (int i = 0; i < max; i++) {
array[n] = i;
if (judge(n)) {
dfs(n + 1);
}
}
}
private static boolean judge(int n) {
for (int i = 0; i < n; i++) {
if (array[i] == array[n] || ((Math.abs(n - i) == Math.abs(array[n] - array[i])) && (n - i < 3))) {
return false;
}
}
return true;
}
}版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/159835.html
