843. n-皇后問題（dfs+輸出各種情況）-有解無憂

n-皇后問題是指將 n 個皇后放在 n?n 的國際象棋棋盤上，使得皇后不能相互攻擊到，即任意兩個皇后都不能處于同一行、同一列或同一斜線上，

現在給定整數n，請你輸出所有的滿足條件的棋子擺法，

輸入格式

共一行，包含整數n，

輸出格式

每個解決方案占n行，每行輸出一個長度為n的字串，用來表示完整的棋盤狀態，

其中”.”表示某一個位置的方格狀態為空，”Q”表示某一個位置的方格上擺著皇后，

每個方案輸出完成后，輸出一個空行，

資料范圍

$1 \leq n \leq 9$

輸入樣例：

輸出樣例：

.Q..
...Q
Q...
..Q.

..Q.
Q...
...Q
.Q..


代碼：

import java.util.Scanner;

public class Main{
        static int n;
        static final int N=10;
        static int a[]=new int[N];
        static char map[][]=new char[N][N];
        static boolean check(int t){
                for(int i=0;i<t;i++)
                    if(a[i]==a[t] || Math.abs(i-t)==Math.abs(a[i]-a[t]))
                        return false;
                return true;
        }
        static void dfs(int t){
                       if(t==n){
　　　　　　　　　　　　　　　　　　　//因為開的字符陣列大小為N，實際輸出可不是N，所以兩重回圈輸出
                                for(int i=0;i<n;i++) {
                                    for(int j=0;j<n;j++)
                                        System.out.print(map[i][j]);
                                    System.out.println();
                                }
                                System.out.println();
                       }
                       for(int i=0;i<n;i++){
                                 a[t]=i;
                                 if(check(t)) {
                                     map[t][i]='Q';
                                     dfs(t+1);
                                     map[t][i]='.';
                                 }
                       }
        }
        public static void main(String[] args) {
                Scanner scan=new Scanner(System.in);
                n=scan.nextInt();
                for(int i=0;i<n;i++)
                    for(int j=0;j<n;j++)
                        map[i][j]='.';
                dfs(0);
        }
}

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/98382.html

標籤：其他

上一篇：手機通話和短信接受的協議是什么？

下一篇：java通過event socket 和freeswitch 的整個通話流程(outbound模式)