2n皇后

問(wèn)題描述

給定一個(gè)n*n的棋盤(pán)，棋盤(pán)中有一些位置不能放皇后。現(xiàn)在要向棋盤(pán)中放入n個(gè)黑皇后和n個(gè)白皇后，使任意的兩個(gè)黑皇后都不在同一行、同一列或同一條對(duì)角線上，任意的兩個(gè)白皇后都不在同一行、同一列或同一條對(duì)角線上。問(wèn)總共有多少種放法？n小于等于8。

輸入格式
輸入的第一行為一個(gè)整數(shù)n，表示棋盤(pán)的大小。
接下來(lái)n行，每行n個(gè)0或1的整數(shù)，如果一個(gè)整數(shù)為1，表示對(duì)應(yīng)的位置可以放皇后，如果一個(gè)整數(shù)為0，表示對(duì)應(yīng)的位置不可以放皇后。

輸出格式
輸出一個(gè)整數(shù)，表示總共有多少種放法。

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

1 1 1 1

樣例輸出：
2

樣例輸入：
4
1 0 1 1
1 1 1 1
1 1 1 1
1 1 1 1

樣例輸出：

0

思路：基本思路和8皇后相同，不同之處在于情況不僅是位置不同決定的，同一個(gè)位置不同顏色的棋子還有不同的結(jié)果。為了分區(qū)分，用2代表白皇后占的位置，用3代表黑皇后占的位置。我們規(guī)定先放白皇后，首先檢查是否為1，如果不為1則該位置不可放置，continue檢查下一個(gè)位置。如果可放，檢查是否符合約束函數(shù)check()；如果不符合，continue檢查下一個(gè)位置。如果符合，本行放置結(jié)束，執(zhí)行putQueen(m+1, queen)遞歸下一行。同時(shí)注意回溯。

import java.util.Scanner; public class Main {static int n;static int[][] chess;static int count = 0;public static void main(String[] args) { Scanner in = new Scanner(System.in); n = in.nextInt(); chess = new int[n][n];for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { chess[i][j] = in.nextInt(); }}// 白皇后記為2，黑皇后記為3，先放白皇后 putQueen(0, 2); System.out.println(count); } public static void putQueen(int m, int queen) { if (m > n - 1) { if (queen == 2) {putQueen(0, 3);} else {count++;} return; } for (int i = 0; i < n; i++) {// 如果位置為0或者queen已放置，則不能放置if (chess[m][i] ！= 1) {continue;}// 如果可放，則記錄;反之，檢查下一列 if (check(m, i, queen)) { chess[m][i] = queen;} else {continue;}// 繼續(xù)判斷下一行 putQueen(m + 1, queen);// 回溯，這里不用考慮0的位置，因?yàn)樵谏厦嬉呀?jīng)被篩掉了，非常巧妙 chess[m][i] = 1;} } public static boolean check(int row, int col, int queen) { int step = 1;while(row - step >= 0){if(chess[row-step][col] == queen) { //上return false;}if(col-step >= 0 && chess[row-step][col-step] == queen) { //左上return false;}if(col+step < n && chess[row-step][col+step] == queen) { //右上return false;}step++;}return true; } }

總結(jié)

以上是生活随笔為你收集整理的蓝桥杯算法提高----2n皇后的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。