Skip to content

Commit 14b0967

Browse files
fishercoder1534fishercoder1534
committed
add 1219
1 parent f8dd826 commit 14b0967

File tree

3 files changed

+131
-0
lines changed

3 files changed

+131
-0
lines changed

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -62,6 +62,7 @@ _If you like this project, please leave me a star._ ★
6262
|1232|[Check If It Is a Straight Line](https://leetcode.com/problems/check-if-it-is-a-straight-line/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1232.java) | [:tv:](https://www.youtube.com/watch?v=_tfiTQNZCbs) |Easy||
6363
|1228|[Missing Number In Arithmetic Progression](https://leetcode.com/problems/missing-number-in-arithmetic-progression/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1228.java) | |Easy||
6464
|1221|[Split a String in Balanced Strings](https://leetcode.com/problems/split-a-string-in-balanced-strings/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1221.java) | |Easy|Greedy|
65+
|1219|[Path with Maximum Gold](https://leetcode.com/problems/path-with-maximum-gold/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1219.java) | |Medium|Backtracking|
6566
|1217|[Play with Chips](https://leetcode.com/problems/play-with-chips/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1217.java) | |Easy|Array, Math, Greedy|
6667
|1214|[Two Sum BSTs](https://leetcode.com/problems/two-sum-bsts/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1214.java) | |Medium| Binary Search Tree|
6768
|1213|[Intersection of Three Sorted Arrays](https://leetcode.com/problems/intersection-of-three-sorted-arrays/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1213.java) | [:tv:](https://www.youtube.com/watch?v=zceoOrHSHNQ)|Easy||

‎src/main/java/com/fishercoder/solutions/_1219.java

Lines changed: 80 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,80 @@
1+
package com.fishercoder.solutions;
2+
3+
import java.util.LinkedList;
4+
import java.util.Queue;
5+
6+
/**
7+
* 1219. Path with Maximum Gold
8+
*
9+
* In a gold mine grid of size m * n, each cell in this mine has an integer representing the amount of gold in that cell, 0 if it is empty.
10+
* Return the maximum amount of gold you can collect under the conditions:
11+
* Every time you are located in a cell you will collect all the gold in that cell.
12+
* From your position you can walk one step to the left, right, up or down.
13+
* You can't visit the same cell more than once.
14+
* Never visit a cell with 0 gold.
15+
* You can start and stop collecting gold from any position in the grid that has some gold.
16+
*
17+
* Example 1:
18+
* Input: grid = [[0,6,0],[5,8,7],[0,9,0]]
19+
* Output: 24
20+
* Explanation:
21+
* [[0,6,0],
22+
* [5,8,7],
23+
* [0,9,0]]
24+
* Path to get the maximum gold, 9 -> 8 -> 7.
25+
*
26+
* Example 2:
27+
* Input: grid = [[1,0,7],[2,0,6],[3,4,5],[0,3,0],[9,0,20]]
28+
* Output: 28
29+
* Explanation:
30+
* [[1,0,7],
31+
* [2,0,6],
32+
* [3,4,5],
33+
* [0,3,0],
34+
* [9,0,20]]
35+
* Path to get the maximum gold, 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7.
36+
*
37+
* Constraints:
38+
* 1 <= grid.length, grid[i].length <= 15
39+
* 0 <= grid[i][j] <= 100
40+
* There are at most 25 cells containing gold.
41+
* */
42+
public class _1219 {
43+
public static class Solution1 {
44+
public int getMaximumGold(int[][] grid) {
45+
Queue<int[]> queue = new LinkedList<>();
46+
int m = grid.length;
47+
int n = grid[0].length;
48+
for (int i = 0; i < m; i++) {
49+
for (int j = 0; j < n; j++) {
50+
if (grid[i][j] > 0) {
51+
queue.offer(new int[]{i, j});
52+
}
53+
}
54+
}
55+
int maxGold = 0;
56+
while (!queue.isEmpty()) {
57+
int[] start = queue.poll();
58+
boolean[][] visited = new boolean[m][n];
59+
visited[start[0]][start[1]] = true;
60+
maxGold = Math.max(maxGold, backtracking(grid, start, grid[start[0]][start[1]], visited));
61+
}
62+
return maxGold;
63+
}
64+
65+
int[] directions = new int[]{0, 1, 0, -1, 0};
66+
private int backtracking(int[][] grid, int[] start, int gold, boolean[][] visited) {
67+
int max = gold;
68+
for (int i = 0; i < directions.length - 1; i++) {
69+
int nextX = start[0] + directions[i];
70+
int nextY = start[1] + directions[i + 1];
71+
if (nextX >= 0 && nextX < grid.length && nextY >= 0 && nextY < grid[0].length && !visited[nextX][nextY] && grid[nextX][nextY] > 0) {
72+
visited[nextX][nextY] = true;
73+
max = Math.max(max, backtracking(grid, new int[]{nextX, nextY}, gold + grid[nextX][nextY], visited));
74+
visited[nextX][nextY] = false;
75+
}
76+
}
77+
return max;
78+
}
79+
}
80+
}

‎src/test/java/com/fishercoder/_1219Test.java

Lines changed: 50 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,50 @@
1+
package com.fishercoder;
2+
3+
import com.fishercoder.solutions._1219;
4+
import org.junit.BeforeClass;
5+
import org.junit.Test;
6+
7+
import static junit.framework.Assert.assertEquals;
8+
9+
public class _1219Test {
10+
private static _1219.Solution1 solution1;
11+
private static int[][] grid;
12+
13+
@BeforeClass
14+
public static void setup() {
15+
solution1 = new _1219.Solution1();
16+
}
17+
18+
@Test
19+
public void test1() {
20+
grid = new int[][]{
21+
{0, 6, 0},
22+
{5, 8, 7},
23+
{0, 9, 0},
24+
};
25+
assertEquals(24, solution1.getMaximumGold(grid));
26+
}
27+
28+
@Test
29+
public void test2() {
30+
grid = new int[][]{
31+
{1, 0, 7},
32+
{2, 0, 6},
33+
{3, 4, 5},
34+
{0, 3, 0},
35+
{9, 0, 20},
36+
};
37+
assertEquals(28, solution1.getMaximumGold(grid));
38+
}
39+
40+
@Test
41+
public void test3() {
42+
grid = new int[][]{
43+
{0, 0, 19, 5, 8},
44+
{11, 20, 14, 1, 0},
45+
{0, 0, 1, 1, 1},
46+
{0, 2, 0, 2, 0},
47+
};
48+
assertEquals(77, solution1.getMaximumGold(grid));
49+
}
50+
}

0 commit comments

Comments
 (0)