Page 1 of 1

# Finding maximum sum path of matrix from left column to right column

Posted 24 September 2015 - 05:33 AM

Jeff loves playing games, Gluttonous snake( an old game in NOKIA era ) is one of his favourites.
However, after playing gluttonous snake so many times, he finally got bored with the original rules.
In order to bring new challenge to this old game, Jeff introduced new rules :
1. The ground is a grid, with n rows and m columns(1 <= n, m <= 500).
2. Each cell contains a value v (-1 vi 99999), if v is -1, then this cell is blocked, and the snake  ≤  ≤
can not go through, otherwise, after the snake visited this cell, you can get v point.
3. The snake can start from any cell along the left border of this ground and travel until it finally
stops at one cell in the right border.
4. During this trip, the snake can only go up/down/right, and can visit each cell only once.
Special cases :
a. Even in the left border and right border, the snake can go up and down.
b. When the snake is at the top cell of one column, it can still go up, which demands the player to
pay all current points , then the snake will be teleported to the bottom cell of this column and vice
versa.
After creating such a new game, Jeff is confused how to get the highest score. Please help him to write a program to solve this problem.
Input
The first line contains two integers n (rows) and m (columns), (1 <= n, m <= 500), separated by a
single space.
Next n lines describe the grid. Each line contains m integers vi (-1 vi 99999)  ≤   ≤
vi = -1 means the cell is blocked.
Output
Output the highest score you can get. If the snake can not reach the right side, output -1.
Limits
 Memory limit per test : 256 megabytes
 Time limit per test : The faster the better

Skeleton Code
Java
public class Main {
public static void main(String[] args) {
}
}
Sample Test
Input
4 4
-1 4 5 1
2 -1 2 4
3 3 -1 3
4 2 1 2
output
23
Path is as shown below
E:\Kajal\Sem 7\Works\1st.png
Input
4 4
-1 4 5 1
2 -1 2 4
3 3 -1 -1
4 2 1 2
output
22
Path is as shown below
E:\Kajal\Sem 7\Works\2nd.png

This is the whole question that has been given to be completed.
I have managed to design the matrix and obtain max value of the first row of the matrix.
However I cant find a way to compare this value with its neighbours to decide where to move next and also i need to store the positions of the cells i have visited.
```import java.io.*;
import java.util.Scanner;
public class Main
{
public static void main(String[] args) throws IOException
{
int i,j,n,m,score=0, cur_pos, next_pos;
int row=0,col=0;
Scanner s = new Scanner(System.in);

System.out.println("Enter the dimensions of the ground:");
n = s.nextInt();
m = s.nextInt();

int board[][] = new int[n][m];
boolean visit_mat[][] = new boolean [row][col]; // to check the cells visited

System.out.println("Enter values of the board:");
for (i = 0; i < n; i++)
{
for (j = 0; j < m; j++)
{
board[i][j] = s.nextInt();

}
}
System.out.println("The board is:");
for (i = 0; i < n; i++)
{
for (j = 0; j < m; j++)
{
System.out.print(board[i][j] + " ");//output the board
}
System.out.println();
}
//DISPLAYS THE FIRST COLUMN OF MATRIX
int size = board.length;
int start_mat[] = new int[size];
for(i=0;i<size;i++)
{
start_mat[i] = board[i];
System.out.println(start_mat[i]);

}

//NOW FIND MAX VALUE IN FIRST COLUMN SINCE OUTPUT ASKS FOR HIGHEST SCORE THAT CAN BE OBTAINED
int start= start_mat[start_mat.length-1];
System.out.println("Max value "+start);

//System.out.println("First Max value is at position" +board[i]);
if (start == -1) //CHECK IF IT IS TAKING VALUE AT THAT POSITION OR VALUE OF THE POSITION
{
System.out.println("-1");
}
else
{
//ADD FIRST HIGHEST NUMBER TO SCORE
score = score + start; //Starts adding up the score
}

//

//FATE OF CUR_POS WILL BE DECIDED HERE; IE WHICH BOARD[][] CELL IT IS AFTER START

/* if(cur_pos == -1)
{
System.out.println("-1");
}
else
{
score = score + cur_pos;
sol_mat[n][m] = 0; //Mark the cell that is visited
}
*/
int end = board [n][m-1]; //The last value to be added to score will be this
score = score + end;

}
}

```

Is This A Good Question/Topic? 0

Page 1 of 1

 .related ul { list-style-type: circle; font-size: 12px; font-weight: bold; } .related li { margin-bottom: 5px; background-position: left 7px !important; margin-left: -35px; } .related h2 { font-size: 18px; font-weight: bold; } .related a { color: blue; }