# 黄金矿工
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
/**
* @author yagol
* @date 上午10:12
* @desc the description of this class
**/
class Solution1219 {
public static void main(String[] args) {
System.out.println(new Solution1219().getMaximumGold(
new int[][]{{1, 0, 7}, {2, 0, 6}, {3, 4, 5}, {0, 3, 0}, {9, 0, 20}}
));
}
int res = 0;
public int getMaximumGold(int[][] grid) {
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[i].length; j++) {
int tempRes = 0;
deep(grid, i, j, tempRes);
System.out.println("检查的是" + grid[i][j] + ", 此时的最大解是" + res);
}
}
return res;
}
public void deep(int[][] grid, int x, int y, int tempRes) {
int value = grid[x][y];
tempRes += value;
res = Math.max(tempRes, res);
grid[x][y] = 0;
for (int i = 0; i < 4; i++) {
int checkX = x, checkY = y;
switch (i) {
case 0:
checkX = x + 1;
break;
case 1:
checkX = x - 1;
break;
case 2:
checkY = y + 1;
break;
case 3:
checkY = y - 1;
break;
default:
break;
}
if (checkX < grid.length && checkX >= 0 && checkY < grid[0].length && checkY >= 0 && grid[checkX][checkY] != 0) {
deep(grid, checkX, checkY, tempRes);
}
}
grid[x][y] = value;
}
}
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
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