蓝桥杯 算法提高 八皇后改 JAVA实现

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

那么这题是典型的回溯算法题目，这题参考了这篇所文章使用的思路https://blog.csdn.net/liuchuo/article/details/51990248?depth_1-utm_source=distribute.pc_relevant.none-task&utm_source=distribute.pc_relevant.none-task
我觉得很棒而且高效。

算法分析

八皇后问题每一行必然会有一个皇后，所以我们只要具体分析每个皇后的所在的列的索引位置即可，代码中用pos[]来定义，即八个皇后分别对应的列索引。

import java.util.*;
public class 八皇后改 {
    static int maxvalue=0;
    static int[][] pic=new int[8][8];

    static boolean check(int pos[],int row){
        /*
        对于八皇后的放置，每行只可能出现一次皇后
        * pos:存放八个皇后的位置
        * row:当前所在行数
        * */
        for(int i=0;i<row;i++){
            if(pos[i]==pos[row]|| Math.abs(i-row)==Math.abs(pos[i]-pos[row]))
                return false;
        }
        return true;
    }


    static void dfs(int[] pos,int row){
        /*
        * 从第一行开始遍历，遍历到最后一行了停止
        * pos[i]第i个棋子（位于第i行）的列索引
        */
        if(row==8) {
            int sum = 0;
            for (int i = 0; i < 8; i++)
                sum += pic[i][pos[i]];
            if(sum>maxvalue)
                maxvalue=sum;
            return;
        }

        /*
        pos[i]用于存放列索引位置，
        如果位于第一个列索引位置摆放完毕，
        那么就从下一列开始摆放，即pos[row]++
        */
        for(pos[row]=0;pos[row]<8;pos[row]++){
            if(check(pos,row))
                dfs(pos,row+1);
        }

    }

    public static void main(String[] args){
        int[] pos=new int[8];
        Scanner sc=new Scanner(System.in);
        for(int i=0;i<8;i++){
            for(int j=0;j<8;j++)
                pic[i][j]=sc.nextInt();
        }
        dfs(pos,0);
        System.out.println(maxvalue);
    }
}