明星网页网站制作,舜江建设集团官方网站,做网站编辑需要看什么书,网站二次开发解题思路#xff1a;
递归 回溯#xff08;n皇后问题的变种#xff09;
在 N 皇后问题的解决方案中#xff0c;我们是从棋盘的顶部向底部逐行放置皇后的#xff0c;这意味着在任何给定时间#xff0c;所有未来的行#xff08;即当前行之下的所有行#xff09;都还没…
解题思路
递归 回溯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;}
}
