得之我幸cyz

試題 基礎練習 2n皇后問題

資源限制

時間限制：1.0s 內存限制：512.0MB

問題描述

　　給定一個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

樣例輸入

4 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1

樣例輸出

0

import java.util.Scanner;
?
?
public class 二N皇后問題 {
?
    static int map[][];//存儲地圖
    static int ans=0;//計算方法
    static int n;//地圖的大小
    
    public static boolean judge(int cur,int i,int color){
        for(int j=cur-1;j>=0;j--){//判斷同一列是否有相同顏色的皇后
            if(map[j][i]==color){
                return false;
            }
        }
        for(int j=cur-1,z=i-1;j>=0&&z>=0;j--,z--){//判斷對角線左側是否有相同顏色的皇后
            if(map[j][z]==color){
                return false;
            }
        }
        for(int j=cur-1,z=i+1;j>=0&&z<n;j--,z++){//判斷對角線右側是否有相同顏色的皇后
            if(map[j][z]==color){
                return false;
            }
        }
        return true;
    }
    
    public static void dfs(int cur,int color){
        if(cur==n){//代表黑色放完了
            if(color==2){
                dfs(0,3);
            }
            else{
                ans++;  
            }
            return ;
        }
        for(int i=0;i<n;i++){
            if(map[cur][i]==1&&judge(cur,i,color)){
                map[cur][i]=color;
                dfs(cur+1,color);
                map[cur][i]=1;//狀態恢復
            }
        }
        return;
    }
    
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc=new Scanner(System.in);
        n=sc.nextInt();
        map=new int[n][n];
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                map[i][j]=sc.nextInt();
            }
        }
        dfs(0,2);//2為黑色，3為白色
        System.out.println(ans);
    }
/*
4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
*/
?
}
?

總結

1.n皇后問題主要就是回溯和遞歸的思想。

2.要注意初始化的問題

map=new int[n][n];
//這里要現在最前面聲明靜態變量static int map[][];
//然后再main函數里對他進行初始化，不能寫成map[][]=new int[n][n];

還有這里

static int ans=0;//計算方法

ans要在最前面初始化為0.

3.然后就是要把狀態恢復了，差不多就是這樣