蓝桥杯练习系统 八皇后改 java解答

时间限制：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

package 答案; /* * 2017年1月14日21:20:29 */ import java.util.*; public class 八皇后改 { static int[][] pic = new int[8][8]; static int maxvalue = 0; public static void main(String[] args){ Scanner sc = new Scanner(System.in); int[] pos = new int[8];//pos存放第i个皇后所在的列 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); } public static void dfs(int[] pos , int row) { if(row == 8) { int sum = 0; for(int i = 0; i < 8;i++) { sum += pic[i][pos[i]];//第i行的皇后在哪一列上 } maxvalue = sum > maxvalue ? sum : maxvalue; return; } for(pos[row] = 0; pos[row] < 8; pos[row]++)//第row个皇后所在的位置从第0列开始试探 { if(issafe(pos ,row))//如果安全，那就准备下一个皇后 { dfs(pos, row+1); } } } public static boolean issafe(int[] pos, int 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; } }