Suppose we have an N x M grid in which each cell of the grid contains a value that is either 0 or a positive integer. An island is a group of values surrounded by 0’s in the orthogonal directions (north, east, south, and west but not diagonally). The problem is to determine the maximum sum between all the islands in the grid. We are given the method called maxValueIsland which takes a 2D array of ints and scans through the grid for islands. Once it finds an island it calls the method getIslandValue which we must implement. The method maxValueIsland then returns the maximum value out of all the island values.
We have been provided with several utility methods that help generate and display the 2D grid.
public static void main(String[] args) {
int map[][] = new int[5][5];
int maxValue = 100;
int dropChance = 25;
randomIslands(map, maxValue, dropChance);
printIslands(map);
System.out.println("There is an island with a value of " + maxValueIsland(map));
}
/********** Student Code Here **************************/
public static int maxValueIsland(int map[][]) {
int maxValue = 0;
for (int r = 0; r < map.length; r++) {
for (int c = 0; c < map[r].length; c++) {
if (map[r][c] != 0) {
int value = getIslandValue(map, r, c);
if (value > maxValue) {
maxValue = value;
}
}
}
}
return maxValue;
}
private static int getIslandValue(int map[][], int r, int c) {
//HERE IS THE METHOD WE MUST IMPLEMENT
}
/******************************************************************/
public static void randomIslands(int map[][], int maxPossibleValue, int chance) {
if (maxPossibleValue <= 0) {
throw new IllegalArgumentException("The max possible value must be a positive integer.");
}
if (chance > 100 || chance < 0) {
throw new IllegalArgumentException("The chance of money drop must be between 0 <= p <= 100");
}
for (int r = 0; r < map.length; r++) {
for (int c = 0; c < map[r].length; c++) {
int possible = (int) (Math.random() * 100) + 1;
if (possible <= chance) {
map[r][c] = (int) (Math.random() * maxPossibleValue) + 1;
}
}
}
}
public static void printIslands(int island[][]) {
int maxDigits = getMaxDigits(island);
for (int r = 0; r < island.length; r++) {
for (int c = 0; c < island[r].length; c++) {
int value = island[r][c];
String s = "%" + maxDigits + "d";
if (value != 0) {
System.out.print(" |");
System.out.printf(s, value);
System.out.print("| ");
} else {
System.out.print(" ");
System.out.printf("%" + maxDigits + "s", "-");
System.out.print(" ");
}
}
System.out.println(" ");
}
}
private static int getMaxDigits(int[][] arr) {
int maxDigitSize = 0;
for (int r = 0; r < arr.length; r++) {
for (int c = 0; c < arr[r].length; c++) {
int value = arr[r][c];
int digits = 0;
while (value != 0) {
digits += 1;
value /= 10;
}
if (digits > maxDigitSize) {
maxDigitSize = digits;
}
}
}
return maxDigitSize;
}
I have tried several iterations and I know that my base case is accurate. I'm having trouble with the recursive call. I need to account for traveling in different directions in the grid. (right, left, up, and down). Here is what I have tried:
private static int getIslandValue(int map[][], int r, int c) {
if (r < 0 || c < 0 || r >= map.length || c >= map[r].length || map[r][c] == 0) {
return 0; // Base Case
}
int right = getIslandValue(map, r, c + 1);
int down = getIslandValue(map, r + 1, c);
int left = getIslandValue(map, r, c - 1);
int up = getIslandValue(map, r - 1, c);
return map[r][c] + (right + left + up + down);
}
I'm getting stackoverflow error. I have tried many different iterations. One of my initial attempts yielded no stackoverflow errors, but it didn't account for traveling left and up:
private static int getIslandValue(int map[][], int r, int c) {
if (r < 0 || c < 0 || r >= map.length || c >= map[r].length || map[r][c] == 0) {
return 0; // Base Case
}
int right = getIslandValue(map, r, c + 1);
int down = getIslandValue(map, r + 1, c);
return map[r][c] + Math.max(right, down);
}
Lastly, I know I must leave a breadcrumb of 0 after I've visited an Island. I would have to include map[r][c] = 0; to accomplish that. But isn't that already accounted for towards the end of my base case? map[r][c] == 0.....??