蓝桥杯17-八皇后*改

女爷i 2023-06-14 06:29 36阅读 0赞

--------------------

title: 蓝桥杯17-八皇后\*改  
date: 2019-11-18 22:24:35  
categories:

*  蓝桥杯  
    tags:
 *  蓝桥杯

--------------------

# 蓝桥杯17-八皇后\*改 #

*  问题描述　　  
    规则同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
    
    49 50 51 52 53 54 55 56
    
    57 58 59 60 61 62 63 64
    
    样例输出260
    
    数据规模和约定　　棋盘上的数字范围0~99
 *  解：使用回溯法
    
        package lanqiao;
        
        import java.util.Scanner;
        
        //问题描述
        //　　规则同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
        public class day_17 { 
            public  static  int[] judge = new int[8];//这个是储存八皇后各行取的数值
            public static int[] book = new int[8];//这个是判断八皇后遍历了多少个，避免重复遍历
            public  static int[][] number;//这个是储存数组
            public static  int max = -1;
            public static void main(String[] args){ 
                Scanner in = new Scanner(System.in);
                number = new int[8][8];
                for(int i=0;i<8;i++){ 
                    for(int j=0;j<8;j++){ 
                        number[i][j] = in.nextInt();
                    }
                }//读取数据
                in.close();
                dfs(0);
                System.out.println(max);
            }
            //遍历数据
            public static void dfs(int num){ 
                if(num==8){ 
                    if(check()==true){ 
                        //判断成功，代表可以计算路径长度了
                        int j = 0;
                        for(int i=0;i<8;i++){ 
                            j+=number[i][judge[i]];
                        }
                        if(j>max){ 
                            max = j;
                        }
                    }
                }
                for(int i=0;i<8;i++){ 
                    if(book[i]==0){ 
                        book[i] =1;
                        judge[num] = i;
                        dfs(num+1);
                        judge[num] = 0;
                        book[i]=0;
                    }
                }
            }
            public static boolean check(){ 
                for(int i=0;i<7;i++){ 
                    for(int j=i+1;j<8;j++){ 
                        if(Math.abs(i-j)==Math.abs(judge[i]-judge[j]))
                            return false;
                    }
                }
                return true;
            }
        }