Jack love playing games, Gluttonous snake( an old game in Nokia era) is one of his favorite. However, after playing gluttonous snake so many times, he finally got bored with the game, so he changed the rules:
Rule 1: Write a code to find the Max sum path in a grid (2-D array), with dimension with n rows and m column (1<=n,m<=500)
Rule 2: In the 2D Array, each cell (elements) contains a value v in the array is from (-1<=v<=99999)
Rule 3. You can start from any position of the leftest column (border) of the array to the rightest(border) column of the array to calculate the Max Sum path.
Rule 4. You can move up, right, down, and CAN'T move left, and can visit each element only one time.
Rule 5.If the element is -1, it means the path is blocked, and you can't go through the path (calculate it in the sum), you have to choose other path to calculate the sum.
For example, if a 4*4 array grid
{{-1,3,2,1}
{2,-1,2,4}
{2,2,-1,3}
{4,2,1,2}};
The max sum path is : (from grid[4][0])
4-->up-->2-->left-->2-->down-->2-->left-->
1-->left-->2-->up-->3-->up-->4-->up-->1
and the sum is 4+2+2+2+1+2+3+4+1 =21
Thank you
Here is my code, I am new in Java and there is still lots of improvements
import java.util.*;
public class MainClass {
public static void main(String[] args) {
@SuppressWarnings("resource")
Scanner rowDimension = new Scanner(System.in);
System.out.print("Enter the number of rows: ");
int firstInput = rowDimension.nextInt();
@SuppressWarnings("resource")
Scanner columnDimension = new Scanner(System.in);
System.out.print("Enter the number of columns: ");
int secondInput = columnDimension.nextInt();
//Input two number to generate 2D Array
Integer [][] array = new Integer[firstInput][secondInput];
//The purpose of the array is check the wall (cell value = -1)
boolean [][] visited = new boolean[firstInput][secondInput];
//Use Math.random() to generate the cell of the array
int[][] randomTable = new int[firstInput][secondInput];
for (int row = 0; row < firstInput; row++) {
for (int column = 0; column < secondInput; column++) {
// multiply by 1000000 to get a number between 0 and 99999
randomTable[row][column] = (int)(Math.random() * 1000000 -1);
System.out.print(randomTable[row][column] + " ");
}
System.out.println();
}
//Start form the left-down location of grid
int i = firstInput-1, j = 0;
visited[i][j] = true;
double sum = array[i][j];
while(true)
{
int max = -1;
int maxi = 0, maxj = 0;
//Case1 : choose path: UP
if(i-1 >= 0 && i-1<= firstInput-1 && j>=0 && j<= secondInput-1 && array[i-1][j] != null && array[i-1][j]>max && !visited[i-1][j])
{
max = array[i-1][j];
maxi = i-1;
maxj = j;
}
//Case2 : choose path: Down
if(i+1 >= 0 && i+1<= firstInput-1 && j>=0 && j<= secondInput-1 &&array[i+1][j] != null && array[i+1][j]>max && !visited[i+1][j])
{
max = array[i+1][j];
maxi = i+1;
maxj = j;
}
//Case3 : choose path: Right
if(i >= 0 && i<= firstInput-1 && j+1>=0 && j+1<= secondInput-1 && array[i][j+1] != null && array[i][j+1]>max && !visited[i][j+1])
{
max = array[i][j+1];
maxi = i;
maxj = j+1;
}
i = maxi;
j = maxj;
visited[i][j] = true;
sum += max;
//To the destination : Right-Up location of the grid
if(i == 0 && j == secondInput-1)
break;
}
System.out.println(sum);
}
}
-3of 3 votes
