Java实现 蓝桥杯VIP 算法训练 王后传说
2024-10-09 06:10:22
问题描述
地球人都知道,在国际象棋中,后如同太阳,光芒四射,威风八面,它能控制横、坚、斜线位置。
看过清宫戏的中国人都知道,后宫乃步步惊心的险恶之地。各皇后都有自己的势力范围,但也总能找到相安无事的办法。
所有中国人都知道,皇权神圣,伴君如伴虎,触龙颜者死……
现在有一个n*n的皇宫,国王占据他所在位置及周围的共9个格子,这些格子皇后不能使用(如果国王在王宫的边上,占用的格子可能不到9个)。当然,皇后也不会攻击国王。
现在知道了国王的位置(x,y)(国王位于第x行第y列,x,y的起始行和列为1),请问,有多少种方案放置n个皇后,使她们不能互相攻击。
输入格式
一行,三个整数,皇宫的规模及表示国王的位置
输出格式
一个整数,表示放置n个皇后的方案数
样例输入
8 2 2
样例输出
10
数据规模和约定
n<=12
import java.util.Scanner;
public class 王后传说 {
private static int[] pos;
private static int x;
private static int y;
private static int cnt;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
pos = new int[n];
x = in.nextInt() - 1;
y = in.nextInt() - 1;
in.close();
dfs(0, n);
System.out.println(cnt);
}
private static boolean isSafe(int row) {
if (Math.abs(row - x) <= 1 && Math.abs(pos[row] - y) <= 1) {
return false;
}
for (int i = 0; i < row; i++) {
if (pos[row] == pos[i] || row - i == Math.abs(pos[row] - pos[i])) {
return false;
}
}
return true;
}
private static void dfs(int row, int n) {
if (row >= n) {
cnt++;
return;
}
for (pos[row] = 0; pos[row] < n; pos[row]++) {
if (isSafe(row)) {
dfs(row + 1, n);
}
}
}
}
最新文章
- HTML常用标签
- hibernate中java类的成员变量类型如何映射到SQL中的数据类型变化
- SqlServer环境配置和卸载
- 数据库连接池原理 与实现(动脑学院Jack老师课后自己的练习有感)
- 使用C++扩展Python的功能 转自:http://blog.csdn.net/magictong/article/details/8897568#comments
- 暑假热身 B. 下载测速
- TCP keepalive
- Notepad++ Shortcuts(Chinese and English Version)
- C指针
- python定制类(以Fib类为例)
- centos 7 最小安装后 ip配置
- 对于ES6中Promise的个人见解
- markdown 字体颜色
- js == 运算规则解析
- 【Mac】-NO.161.Mac.1 -【MacOS Error running &#39;Tomcat 8.5.371&#39;: Cannot run program Permission denied】
- Altium Designer添加元件库文件
- HTML5 History API &; URL 重定向
- JS两个页面通过URL传值
- 自适应阈值二值化之最大类间方差法(大津法,OTSU)
- ecstore-自定义app里增加对应的wap的模板