蓝桥杯 - 受伤的皇后

解题思路：

递归 + 回溯（n皇后问题的变种）

在 N 皇后问题的解决方案中，我们是从棋盘的顶部向底部逐行放置皇后的，这意味着在任何给定时间，所有未来的行（即当前行之下的所有行）都还没有被探查或放置任何皇后。因此，检查下方行是没有意义的，因为它们总是空的。所以只需要检查左上45°和右上45°。

import java.util.Scanner;public class Main {static int count = 0;public static void main(String[] args) {Scanner scan = new Scanner(System.in);int n = scan.nextInt();int[][] arr = new int[n][n];dfs(arr, 0);System.out.println(count);}public static void dfs(int[][] arr, int row) {if (row == arr.length) {count++;return;}// 遍历列,因为n行n列，所以arr.length和arr[0].length是一样的for (int j = 0; j < arr.length; j++) {if (checkValid(arr, row, j)) {arr[row][j] = 1;dfs(arr, row + 1);// 回溯arr[row][j] = 0;}}}public static boolean checkValid(int[][] arr, int row, int col) {// 检查列,因为n行n列，所以row既是行的长度又是列的长度for (int i = 0; i < row; i++) {if (arr[i][col] == 1) {return false;}}// 检查左上45°for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {if (arr[i][j] == 1 && Math.abs(row - i) < 3) {return false;}}// 检查右上45°for (int i = row - 1, j = col + 1; i >= 0 && j < arr.length; i--, j++) {if (arr[i][j] == 1 && Math.abs(row - i) < 3) {return false;}}return true;}
}