-
Notifications
You must be signed in to change notification settings - Fork 1
/
PathWithMaximumGold.java
54 lines (51 loc) · 1.64 KB
/
PathWithMaximumGold.java
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
/**
* 1219. Path with Maximum Gold
* 回溯
* @author LBW
*/
public class PathWithMaximumGold {
private int max = Integer.MIN_VALUE;
public int getMaximumGold(int[][] grid) {
int l = grid.length, c = grid[0].length;
boolean[][] isVisited = new boolean[l][c];
for (int i = 0; i < l; i++) {
for (int j = 0; j < c; j++) {
if (grid[i][j] > 0) {
dfs(grid, 0, isVisited, i, j);
//backTrack
isVisited[i][j] = false;
}
}
}
return max;
}
private boolean isValid(int[][] grid, boolean[][] isVisited, int i, int j) {
if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == 0 || isVisited[i][j])
return false;
else
return true;
}
private void dfs(int[][] grid, int cur, boolean[][] isVisited, int i, int j) {
cur += grid[i][j];
isVisited[i][j] = true;
if (cur > max)
max = cur;
if (isValid(grid, isVisited, i - 1, j)) {
dfs(grid, cur, isVisited, i - 1, j);
//backtrack
isVisited[i-1][j] = false;
}
if (isValid(grid, isVisited, i + 1, j)) {
dfs(grid, cur, isVisited, i + 1, j);
isVisited[i+1][j] = false;
}
if (isValid(grid, isVisited, i, j + 1)) {
dfs(grid, cur, isVisited, i, j + 1);
isVisited[i][j + 1] = false;
}
if (isValid(grid, isVisited, i, j - 1)) {
dfs(grid, cur, isVisited, i, j - 1);
isVisited[i][j - 1] = false;
}
}
}