Time: 1h 15m
Problem Statement
A chessboard of size N * M (i.e. N rows and M columns) is given. Each
field of the chessboard can be indexed using a pair of integers (P, Q)
where 0 <= P < N and 0 <= Q < M.
On each field of the chessboard there lies a number of rice grains. A
pawn is initially located at field (0, 0). It can perform two kinds of
moves:
- move from field (P, Q) to field (P+1, Q), or
- move from field (P, Q) to field (P, Q+1).
After N + M - 2 moves the pawn will arrive at field (N-1, M-1). During its
movement through the chessboard it collects all the rice grains from the
fields it stands on.
Write a function
class Test { public int solution(int[][] A); }
that given a matrix of size N * M describing the number of rice grains
lying on each field of a N * M chessboard returns the maximal number of
rice grains a pawn can collect while moving from the field (0, 0) to the
field (N-1, M-1) in the manner specified above. Assume that . Assume that
each element of the matrix is a non-negative integer not exceeding 200.
For example, given matrix A such that
A[0][0]=2 A[0][1]=2 A[0][2]=3 A[0][3]=0
A[1][0]=0 A[1][1]=3 A[1][2]=1 A[1][3]=1
A[2][0]=1 A[2][1]=2 A[2][2]=2 A[2][3]=1
A[3][0]=4 A[3][1]=1 A[3][2]=2 A[3][3]=2
the function should return 15.
One of the paths that the pawn can take : A[0][0], A[0][1], A[1][1],
A[2][1], A[2][2], A[3][2], A[3][3]
Following this path the pawn will collect A[0][0] + A[0][1] + A[1][1] +
A[2][1] + A[2][2] + A[3][2] + A[3][3] = 2 + 2 + 3 + 2 + 2 + 2 + 2 = 15
rice grains. There is no path the pawn can take to collect more than 15
rice grains.
Assume that:
- N and M are integers in the range [0...1000]
- each element of matrix A is an integer within the range [0...200]
Complexity:
- expected worst-case time complexitiy is O(N*M)
- expected worst-case space complexitiy is O(N+M)