CSC 385: Recursion Assignment
For this assignment, you are given a main class, Islands.java.Do not change any of the utility methods in Islands.java.You may modify the main method for testing such as changing the dropChance and maxValue variables as well as modifying the size of the 2D array called map.
You may add all necessary methods to solve this problem.You 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 you must implement.The method maxValueIsland then returns the maximum value out of all the island values.
The Problem
Suppose you have and 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.Here is an example
In this grid there are 4 islands.The island with 45, 20, 43, and 4.The island with 46 and 22.The island with just 9.And the island with 31, 30, 31, and 50.The maximum value between all these islands is 142 which is the island with 31, 30, 31, and 50.Something to note is that just because an island has a lot of values or is big doesn’t mean it is the most valued island.Here is an example of a grid where the value of an island with one value is more than the island with 5 values.
01000
12100
01000
00080
00000
In the above grid, there is an island valued at 6 and an island valued at 8.The 8 should be returned according to the problem statement.
The Code
I have provided several utility methods to help generate and display the 2D grid.Here is a listing of those methods
randomIslands(int map[][], int maxPossibleValue, int chance)-This takes a 2D array of integers and will randomly decide whether to place a value at a location.maxPossibleValueis the maximum possible value.The value is random between 1 andmaxPossibleValue.Chanceis the percentage a non-zero value gets placed at a location.All other locations will have a zero.
printIslands(int island[][]) –This takes a 2D array of integers and printsa representation of the 2D array.Any non-zero value will be surrounded by pipebars ( | ) while zeroes are printed as hyphens ( - ).This makes it easy to see the islands for testing.Here is an example print
-----
|32|-|68|--
-|76|---
----|21|
----|37|
getMaxDigits(int arr[][])– This is used byprintIslandsand isn’t really useful for anything but its specific use case.
getIslandValue(int map[][], int row, int col) –This is the method you must implement.It accepts a 2D array of ints.The row and column (row and col) which is the location for the start of an island.
Assignment Requirements
You must finish the getIslandValue method. It must utilize recursion to get the value of an island and return its total.