目? ?錄

題目描述

題解

【算法】八皇后，藍橋杯2n皇后 算法思路詳細講解（Java）

---

題目描述

題目描述
給定一個 n × n 的棋盤，棋盤中有一些位置不能放皇后。

現在要向棋盤中放入 n 個黑皇后和 n 個白皇后，使任意的兩個黑皇后都不在同一行、同一列或同一條對角線上；

任意的兩個白皇后都不在同一行、同一列或同一條對角線上。

問總共有多少種放法？n 小于等于 8。

輸入格式
輸入的第一行為一個整數 n，表示棋盤的大小。
接下來 n 行，每行 n 個 0 或 1 的整數，整數為 1，表示該位置可以放皇后；整數為 0，表示該位置不可以放皇后。

輸出格式
輸出一個整數，表示總共有多少種放法。

樣例輸入
4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1

樣例輸出
2

題解

原文鏈接

package B基礎練習;import java.util.*;public class A27_2n皇后2 {static int n;static int count = 0; // 統計static boolean flag = true; // 用于標記是在放白棋子還是黑棋子public static void main(String[] args) {Scanner scanner = new Scanner(System.in);n = scanner.nextInt();int[][] arr = new int[n][n];int[] white = new int[n];int[] black = new int[n];for (int i = 0; i < n; i++) {white[i] = Integer.MAX_VALUE;black[i] = Integer.MAX_VALUE;}for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {arr[i][j] = scanner.nextInt();}}dfs(arr, white, black, 0);System.out.println(count);}private static void dfs(int[][] arr, int[] white, int[] black, int row) {if (row == white.length) {if (flag) {flag = !flag;// 用交換參數位置，進行黑色棋子的擺放dfs(arr, black, white, 0);// 白色棋子放完后，開始放黑色棋子flag = !flag;// 回溯} else {// 兩種棋子都放完了count++;}return;}for (int i = 0; i < n; i++) {if (check(arr, white, row, i)) {white[row] = i;if (flag)arr[row][i] = 2;elsearr[row][i] = 3;dfs(arr, white, black, row + 1);white[row] = Integer.MAX_VALUE;arr[row][i] = 1;// 回溯}}}private static boolean check(int[][] arr, int[] a, int x, int y) {if (arr[x][y] == 2)return false;// 白色棋子占了if (arr[x][y] == 0)return false;// 這個位置不能放皇后for (int i = 0; i < a.length; i++) {if (a[i] == y)// 檢查列return false;if (i - a[i] == x - y)// 檢查主對角線return false;if (i + a[i] == x + y)// 檢查副對角線return false;}return true;}}

【算法】八皇后，藍橋杯2n皇后 算法思路詳細講解（Java）

package B基礎練習;public class A27_2n皇后 {static int n = 4, count; // n階棋盤public static void main(String[] args) {int[][] mainChess = new int[n][n]; // for (int i = 0; i < n; i++) { // Java數組初始化元素默認為0 // for (int j = 0; j < n; j++) { // mainChess[i][j] = 0; // } // }putChess(0, mainChess);}public static void putChess(int row, int[][] chess) {int[][] currentChess = (int[][]) chess.clone();if (row == n) {count++;System.out.println("第" + count + "種：");for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {System.out.print(currentChess[i][j]);}System.out.println();}System.out.println();return;} else {for (int i = 0; i < n; i++) {if (!isDanger(row, i, currentChess)) {for (int j = 0; j < n; j++) {currentChess[row][j] = 0;}currentChess[row][i] = 1;putChess(row + 1, currentChess);}}}}public static boolean isDanger(int row, int col, int[][] currentChess) {for (int i = 0; i < row; i++) {if (currentChess[i][col] == 1) {return true;}for (int j = 0; j < n; j++) {if (((row + col) == (i + j) || (row - col) == (i - j)) && currentChess[i][j] == 1) {return true;}}}return false;}}

?

總結

以上是生活随笔為你收集整理的蓝桥杯 基础练习 2n皇后的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。