Java实现蓝桥杯 算法提高 八皇后 改
2024-10-21 03:21:59
**算法提高 8皇后·改**
时间限制：1.0s 内存限制：256.0MB
提交此题
问题描述
规则同8皇后问题，但是棋盘上每格都有一个数字，要求八皇后所在格子数字之和最大。
输入格式
一个8*8的棋盘。
输出格式
所能得到的最大数字和
样例输入
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
48 50 51 52 53 54 55 56
57 58 59 60 61 62 63 64
样例输出
260
数据规模和约定
棋盘上的数字范围0~99
import java.util.Scanner;
public class bahuanghougai {
public static int sum = 0;
public static int max = Integer.MIN_VALUE;
public static boolean [] col = new boolean [9];
public static boolean [] row = new boolean [9];
public static int [] hash = new int [9];
public static boolean [] [] bool = new boolean [9][9];
public static int [] [] num = new int [9][9];
public static void main(String[] args) {
Scanner sc =new Scanner(System.in);
for (int i = 1; i <9; i++) {
for (int j = 1; j < 9; j++) {
num[i][j]=sc.nextInt();
}
}
f(1);
System.out.println(max);
}
public static void f(int step){
if(step==9){
max=Math.max(sum, max);
return;
}
for (int i = 1; i <= 8; i++) {
if (isConfilct(step, i)) {
continue;
} else {
hash[step] = i;
sum+=num[step][i];
f(step + 1);
sum-=num[step][i];
hash[step] = -1;
}
}
}
private static boolean isConfilct(int row, int column) { //一行一个皇后，第n个皇后也代表着第n行
if(row == 1){//第1行永远不会冲突
return false;
}
//只需要保证与那些已经就位的皇后不冲突即可
for (int i = 1; i < row; i++) {
if (hash[i] == column || ( column - row) == (hash[i] - i) || (row - column)== (i-hash[i])
|| (row + column) == (hash[i] + i)) {
return true;
}
}
return false;
}
}
最新文章
- C、C++： 引用、指针、实例、内存模型、namespace
- 使用zfs进行pg的pitr恢复测试
- AlwaysOn可用性组功能测试（一）--AlwaysOn故障转移测试
- php 生日提醒程序
- eclipse 怎么新建工作空间workspace
- ASP 发送邮件
- 硬件相关-EMI & EMS & EMC
- 笔记一：Python的PyDev插件在eclipse上面安装（新的插件地址 location）
- node防xss攻击插件
- Unity3d项目入门之打Apk包
- mysql主从复制（半同步方式）
- PHP性能分析——xhprof（window 安装xhporf）
- Redis与Mysql数据同步
- HIBERNATE与 MYBATIS的对比
- Webpack 常用命令总结以及常用打包压缩方法
- window.location对象详解
- CSS-设置Footer始终在页面底部
- System.Web.HttpValueCollection.ThrowIfMaxHttpCollectionKeysExceeded
- Oracle中TO_DATE TO_CHAR格式
- mybatis 之 resultType="HashMap" parameterType="list"