洛谷 P1219 八皇后问题 回溯 Java

洛谷 P1219 八皇后问题

import java.util.ArrayList;
import java.util.Scanner;
import java.util.Stack;
/*** 八皇后问题* @author wangshaoyu*/
public class Main {
    static int n;static int ans = 0;static ArrayList<ArrayList<Integer>> list = new ArrayList<>();static Stack<Integer> stack = new Stack<>();static boolean[] rows; // 用于标记这一行是否已经放过棋子了static boolean[] cols; // 用于标记这一列是否已经放过棋子了// 关于对角线的表示：// 斜向左这条对角线 i + j 会呈现递增0，1，2，--- n + 1.// 斜向右这条对角线 i - j = -2，-1，0，1，2.static boolean[] zuo; // 用于标记斜向左这些对角线是否已经放过棋子了static boolean[] you; // 用于标记斜向右这些对角线是否已经放过棋子了public static void main(String[] args) {
    Scanner in = new Scanner(System.in);n = in.nextInt();rows = new boolean[n];cols = new boolean[n];// 注意数组大小zuo = new boolean[n * 2 - 1];you = new boolean[n * 2 - 1];dfs(0, 0);// 输出前三行以及总数StringBuilder sb = new StringBuilder();for (int i = 0; i < 3; i++) {
    ArrayList<Integer> al = list.get(i);for (Integer integer : al) {
    sb.append(integer).append(" ");}sb.deleteCharAt(sb.length() - 1);sb.append("\n");}System.out.print(sb);System.out.println(ans);}/*** 在每一层 dfs 都选一个可以放的位置，如果这一行都没有可以放的位置，就会回到上一层的 dfs* @param count 已经摆放好的棋子的数量* @param s 在第 s 行放棋子*/static void dfs(int count, int s) {
    // 如果棋子都放好了，就可以返回了if (count == n) {
    ans++;list.add(new ArrayList<>(stack));return;}for (int j = 0; j < n; j++) {
    if (rows[s] == false && cols[j] == false && zuo[s + j] == false && you[s - j + n - 1] == false) {
    rows[s] = true;cols[j] = true;zuo[s + j] = true;you[s - j + n - 1] = true;stack.push(j + 1);// 需要从当前行的下一行开始放dfs(count + 1, s + 1);stack.pop();rows[s] = false;cols[j] = false;zuo[s + j] = false;you[s - j + n - 1] = false;}}}
}