CareerCup

I didn't understood the question nor the example output they showed. It's a 2-D array with 4 grids? and movements are not clear to me.

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.

class Solution(object):
def maxPath(self,grid):
if not grid or not grid[0]:
return 0
res = 0
for i in xrange(len(grid)):
if grid[i][0] != -1:
sumRes = []
self.dfs(grid,i,0,0,sumRes)
res = max(res,max(sumRes))
return res
def dfs(self,grid,i,j,path,sumRes):
if j<0 or j==len(grid[0]) or i<0 or i==len(grid) or grid[i][j] == -1:
return
if j == len(grid[0])-1 and (i+1==len(grid) or grid[i+1][j] == -1) and (i-1<0 or grid[i-1][j] == -1):
sumRes.append(path+grid[i][j])
return
temp = grid[i][j]
grid[i][j] = -1
self.dfs(grid,i-1,j,path+temp,sumRes)
self.dfs(grid,i+1,j,path+temp,sumRes)
self.dfs(grid,i,j+1,path+temp,sumRes)
grid[i][j] = temp
return sumRes

class Solution(object):
    def maxPath(self,grid):
        if not grid or not grid[0]:
            return 0
        res = 0
        for i in xrange(len(grid)):
            if grid[i][0] != -1:
                sumRes = []
                self.dfs(grid,i,0,0,sumRes)
                res = max(res,max(sumRes))
        return res
    def dfs(self,grid,i,j,path,sumRes):
        if j<0 or j==len(grid[0]) or i<0 or i==len(grid) or grid[i][j] == -1:
            return
        if j == len(grid[0])-1 and (i+1==len(grid) or grid[i+1][j] == -1) and (i-1<0 or grid[i-1][j] == -1):
            sumRes.append(path+grid[i][j])
            return
        temp = grid[i][j]
        grid[i][j] = -1
        self.dfs(grid,i-1,j,path+temp,sumRes)
        self.dfs(grid,i+1,j,path+temp,sumRes)
        self.dfs(grid,i,j+1,path+temp,sumRes)
        grid[i][j] = temp
        return sumRes

class Solution(object):
    def maxPath(self,grid):
        if not grid or not grid[0]:
            return 0
        res = 0
        for i in xrange(len(grid)):
            if grid[i][0] != -1:
                sumRes = []
                self.dfs(grid,i,0,0,sumRes)
                res = max(res,max(sumRes))
        return res
    def dfs(self,grid,i,j,path,sumRes):
        if j<0 or j==len(grid[0]) or i<0 or i==len(grid) or grid[i][j] == -1:
            return
        if j == len(grid[0])-1 and (i+1==len(grid) or grid[i+1][j] == -1) and (i-1<0 or grid[i-1][j] == -1):
            sumRes.append(path+grid[i][j])
            return
        temp = grid[i][j]
        grid[i][j] = -1
        self.dfs(grid,i-1,j,path+temp,sumRes)
        self.dfs(grid,i+1,j,path+temp,sumRes)
        self.dfs(grid,i,j+1,path+temp,sumRes)
        grid[i][j] = temp
        return sumRes

class Solution(object):
    def maxPath(self,grid):
        if not grid or not grid[0]:
            return 0
        res = 0
        for i in xrange(len(grid)):
            if grid[i][0] != -1:
                sumRes = []
                self.dfs(grid,i,0,0,sumRes)
                res = max(res,max(sumRes))
        return res
    def dfs(self,grid,i,j,path,sumRes):
        if j<0 or j==len(grid[0]) or i<0 or i==len(grid) or grid[i][j] == -1:
            return
        if j == len(grid[0])-1 and (i+1==len(grid) or grid[i+1][j] == -1) and (i-1<0 or grid[i-1][j] == -1):
            sumRes.append(path+grid[i][j])
            return
        temp = grid[i][j]
        grid[i][j] = -1
        self.dfs(grid,i-1,j,path+temp,sumRes)
        self.dfs(grid,i+1,j,path+temp,sumRes)
        self.dfs(grid,i,j+1,path+temp,sumRes)
        grid[i][j] = temp
        return sumRes

import java.lang.*;
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);

}
}

/*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:)*/