刷题 DFS : 受伤的皇后 （python, java）

刷题 DFS : 受伤的皇后 （python, java）

https://www.lanqiao.cn/problems/552/learning/

输入输出样例

示例 1

输入

4
1

输出

2
1

思路：放置皇后是最经典的DFS递归题目了。思路是先遍历第一行的位置，如果位置符合条件，就放置皇后；接下来立刻递归遍历第二行的位置，如果遇到位置符合的就放置皇后，否则放弃这条递归路径；之后重复步骤。
`

上面是主要思路，而要完成这个思路，需要一个全局变量存储当前已经放置了的皇后的位置信息。这样才可以在遍历新的一行时和其他皇后位置对比，看是否符合条件。

Python

# 全局变量
n = 0
count = 0  # 统计放置的方案
arr = [0 for _ in range(100)] # 存储皇后放置的位置。arr[r]=c r表示行，c表示列


def dfs(r):
    """
    DFS
    :param r: 表示当前递归的行数。也可以解读为已经放置皇后的个数。
    :return:
    """
    # 正常结束条件，走完第n行结束递归。因为走到r==n表明已经放置了n个皇后了。
    global count
    if r == n:
        count += 1
    else:
        # 如果r还没有走到底，就遍历下一行
        for c in range(n):
            # 如果当前位置合法，就进入下一行的寻找
            if check(r, c):
                arr[r] = c
                dfs(r + 1)  # 递归


def check(r, c):
    """
    检查当前位置是否符合放置皇后的条件
    :param r: 行号
    :param c: 列号
    :return:
    """
    for i in range(r):
        if arr[i] == c:
            return False
        if abs(r - i) == abs(c - arr[i]) and r - i < 3:
            return False
    return True


if __name__ == "__main__":
    n = int(input())  # 棋盘的大小，也是皇后的个数
    dfs(0)
    print(count)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

java

import java.util.Scanner;

public class Main {
	// 为了方便，使用全局静态变量存储
	static int n = 0; //皇后个数
	static int sum = 0;  // 统计放置的方案数
	static int[] a = new int[100]; //存储皇后放置的位置。a[r]=c r表示行，c表示列
	
	public static void dfs(int r) {
		//结束条件，走完第n行结束递归
		if (r==n) {
			sum++;
		} else {
			// 如果r还没有走到底，就遍历下一行
			for (int c = 0; c < n; c++) {
				// 如果当前位置合法，就进入下一行的寻找
				if (check(r, c)) {
					a[r] = c;
					dfs(r+1);// 下一行
				}
				//如果不合法就结束递归
			}
		}
	}
	
	public static boolean check(int r, int c) {
		// 和之前的皇后位置对比是否合法
		for (int i = 0; i < r; i++) {
			//保证不同列
			if (a[i]==c) {
				return false;
			}
			// 保证对角线的行数 >=3
			if (Math.abs(r-i)==Math.abs(c-a[i]) && (r-i) <3) {
				return false;
			}
		}
		return true;
	}
	
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		n = scan.nextInt();
		dfs(0);
		System.out.println(sum);
		
	}

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49