[Java] 蓝桥杯ADV-203 算法提高 8皇后·改

问题描述
规则同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

package adv203;

import java.util.Scanner;

public class Main {
    private static int[][] cheese = new int[8][8];

    private static int[] pos = new int[8];

    private static int maxValue = 0;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 8; j++) {
                cheese[i][j] = in.nextInt();
            }
        }
        in.close();
        dfs(0, 0);

        System.out.println(maxValue);
    }

    private static boolean isOk(int row) {
        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 maxTempValue) { if (row >= 8) {
            maxValue = Integer.max(maxValue, maxTempValue);
            return;
        }

        for (pos[row] = 0; pos[row] < 8; pos[row]++) {
            if (isOk(row)) {
                dfs(row + 1, maxTempValue + cheese[row][pos[row]]);
            }
        }
    }
}

package adv203;

import java.util.Scanner;

public class Main {

private static int[][] cheese = new int[8][8];

private static int[] pos = new int[8];

private static int maxValue = 0;

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

for (int i = 0; i < 8; i++) {

for (int j = 0; j < 8; j++) {

cheese[i][j] = in.nextInt();

}

in.close();

dfs(0, 0);

System.out.println(maxValue);

}

private static boolean isOk(int row) {

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 maxTempValue) { if (row >= 8) {

maxValue = Integer.max(maxValue, maxTempValue);

return;

}

for (pos[row] = 0; pos[row] < 8; pos[row]++) {

if (isOk(row)) {

dfs(row + 1, maxTempValue + cheese[row][pos[row]]);

}

❤ 点击这里 -> 订阅《PAT | 蓝桥 | LeetCode学习路径 & 刷题经验》by 柳婼

❤ 点击这里 -> 订阅《从放弃C语言到使用C++刷算法的简明教程》by 柳婼

❤ 点击这里 -> 订阅PAT甲级乙级、蓝桥杯、GPLT天梯赛、LeetCode题解离线版