## mirrorme

BAN USER- 0of 0 votes

AnswersJack 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:

- mirrorme in United States

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);

}

}| Report Duplicate | Flag | PURGE

TATA Consultancy Services Software Developer Java

Take an example in question, I mean a 2D-array with dimension 4*4 (row=4, column=4) and we want find the Max sum path.

According to rule 1, so we start from the grid[4][0] location (fourth rows and first column), and its value is 4.

and go find the next element(cell) to reach the max sum path.

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

import java.lang.*;

- mirrorme March 13, 2016import 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);

}

}

/*Hello, Ziqiyang88,

I follow your pseudo code for reference, sorry I am very new in Java.

Here is my code, and there is a bug in my code.

"Exception in thread "main" java.lang.NullPointerException"

If you are available, would you please take a look my code? Thank you:)*/