2021模拟赛 受伤的皇后 dfs

和此题同类型：https://blog.csdn.net/weixin_51995229/article/details/123402884

2. 与上题不同的时 ，加了个宽松的条件，两个皇后在同一条 45 度角的斜线上，这两个皇后之间行号的差值至少为 3 ，就是说，斜线上可以放多个，只要满足差值的条件；
3. 在八皇后问题，dfs搜的是行，递归出口就是搜完了最后一行；在dfs中进入到第u行时 ，我们要去搜索当前行的每一列，如果某一列可以放皇后的话，我们去把它标记为1，然后dfs向下搜索，还要记得回溯；

import java.util.Scanner;

public class Main {
	static int map[][] = new int[15][15];
	static int n;
	static int ans = 0;

	// 检查(x,y)这个点是否可以放皇后
	static boolean check(int x, int y) {
		// 行
		for (int i = 0; i < n; i++) {
			if (map[x][i] == 1)
				return false;
		}
		// 列
		for (int i = 0; i < n; i++) {
			if (map[i][y] == 1)
				return false;
		}
		// 左上到右下
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (i - j == x - y)
					if (map[i][j] == 1 && Math.abs(x - i) < 3)//两个皇后之间行号的差值至少为 3
						return false;
			}
		}
		// 右上到左下
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (i + j == x + y)
					if (map[i][j] == 1 && Math.abs(x - i) < 3)//两个皇后之间行号的差值至少为 3
						return false;
			}
		}

		return true;
	}

	static void dfs(int u) {// u:当前搜索的第u行
		if (u == n) {
			ans++;
			return;
		}
		// 搜索这一行的所有列，看看是否可以放皇后
		for (int i = 0; i < n; i++) {
			if (check(u, i)) {//可以放的话在往下一行搜索，否则这个路线已经走不了了
				map[u][i] = 1;
				dfs(u + 1);
				map[u][i] = 0;//回溯
			}
		}
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		dfs(0);// 从第一行开始搜索
		System.out.println(ans);
	}
}