題目描述
小藍在一個 n行 m列的方格圖中玩一個游戲，
開始時，小藍站在方格圖的左上角，即第 11 行第 11 列，
小藍可以在方格圖上走動，走動時，如果當前在第 r 行第 c列，他不能走到行號比 r 小的行，也不能走到列號比 c 小的列，同時，他一步走的直線距離不超過 33，
例如，如果當前小藍在第 33 行第 55 列，他下一步可以走到第 33 行第 66 列、第 33 行第 77 列、第 33 行第 88 列、第 44 行第 55 列、第 44 行第 66 列、第 44 行第 77 列、第 55 行第 55 列、第 55 行第 66 列、第 66 行第 55 列之一，
小藍最終要走到第 n行第 m 列，
在圖中，有的位置有獎勵，走上去即可獲得，有的位置有懲罰，走上去就要接受懲罰，獎勵和懲罰最終抽象成一個權值，獎勵為正，懲罰為負，
小藍希望，從第 11 行第 11 列走到第 n 行第 m 列后，總的權值和最大，請問最大
輸入描述
輸入的第一行包含兩個整數 n,m表示圖的大小，
接下來 n行，每行 m個整數，表示方格圖中每個點的權值，
輸出：
輸出一個整數，表示最大權值和，
示例 1
輸入：
3 5
-4 -5 -10 -3 1
7 5 -9 3 -10
10 -2 6 -10 -4
輸出：
15
動態規劃+深度優先搜索
解題代碼
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int x = scanner.nextInt();
int y = scanner.nextInt();
int[][] arr = new int[x][y];
for(int i = 0;i<x;i++) {
for(int j = 0;j<y;j++) {
arr[i][j] = scanner.nextInt();
}
}
int result = dfs(arr,0,0);
System.out.println(result);
}
static int dfs(int[][]arr, int x, int y) {
if(x==arr.length-1 && y == arr[0].length-1) {
return arr[x][y];
}
int[]a = new int[] {1,2,3,0,0,0,1,1,2};
int[]b = new int[] {0,0,0,1,2,3,1,2,1};
int max = Integer.MIN_VALUE;
for(int i = 0;i<a.length;i++) {
if(x+a[i]>=arr.length || y+b[i]>=arr[0].length) {
continue;
}
max = Math.max(dfs(arr,x+a[i], y+b[i]), max);
}
return max+ arr[x][y];
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/375048.html
標籤：其他
上一篇：開心小游戲