受伤的皇后（dfs）

蔚落 2024-03-31 13:11 29阅读 0赞

#### 记录一道dfs的题目， ####

#### 这道题对于刚接触dfs的同学来说算是一道不错的题目了， ####

#### 能够帮助我们理解得更深刻... ####

题目：受伤的皇后

#### 题目描述 ####

有一个 n×n 的国际象棋棋盘（n 行 n 列的方格图），请在棋盘中摆放 n 个受伤的国际象棋皇后，要求：

1.  任何两个皇后不在同一行。
2.  任何两个皇后不在同一列。
3.  如果两个皇后在同一条 45 度角的斜线上，这两个皇后之间行号的差值至少为 3 。

请问一共有多少种摆放方案。

#### 输入描述 ####

输入的第一行包含一个整数 nn。

其中，1≤n≤10。

#### 输出描述 ####

输出一个整数，表示答案。

#### 输入输出样例 ####

示例 1

输入

输出

#### 运行限制 ####

*  最大运行时间：1s
 *  最大运行内存: 128M

import java.io.*;
    
    public class Main {
        static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    
        static int max;
        static int[] array = new int[10];
        static int count = 0;//解法数目
    
        public static void main(String[] args) throws IOException {
            String readLine = br.readLine();
            max = Integer.parseInt(readLine);
            dfs(0);
            bw.write(String.valueOf(count));
            bw.flush();
            br.close();
            bw.close();
        }
    
        private static void dfs(int n) {
            if (n == max) {
                count++;
                return;
            }
            for (int i = 0; i < max; i++) {
                array[n] = i;
                if (judge(n)) {
                    dfs(n + 1);
                }
            }
    
        }
    
        private static boolean judge(int n) {
            for (int i = 0; i < n; i++) {
                if (array[i] == array[n] || ((Math.abs(n - i) == Math.abs(array[n] - array[i])) && (n - i < 3))) {
                    return false;
                }
            }
            return true;
        }
    
    }