[USACO1.5] 八皇后 Checker Challenge Java

import java.util.*;public class Main {// 标记 对角线1，对角线2，所在x轴 是否存在棋子static boolean[] d1 = new boolean[100], d2 = new boolean[100], d = new boolean[100]; static int n, ans = 0;static int[] arr = new int[14]; // 记录一轮棋子位置(x, y)public static void main(String[] args) {Scanner sc = new Scanner(System.in);n = sc.nextInt();sc.close();dfs(1);System.out.println(ans);}static void dfs(int x) {if (x > n) { // 找到一组解ans++;if (ans <= 3) { // 输出前3个解for (int i = 1; i <= n; i++) System.out.print(arr[i] + " ");System.out.println();}return;}for (int y = 1; y <= n; y++) {// 判断两条对角线以及所在x轴是否已经存在棋子if (d[y] || d1[x + y] || d2[x - y + n]) continue; setChecked(x, y, true); // 放置棋子dfs(x + 1); // 下一列继续搜索setChecked(x, y, false); // 重置状态}}static void setChecked(int x, int y, boolean flag) {arr[x] = y; // (x, y)第x行y列放置一颗棋子d[y] = flag;d1[x + y] = flag;d2[x - y + n] = flag;}
}

每日一水~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~