THIS PROBLEM NEEDS TO BE CODED IN JAVA BECAUSE THERE IS NO C++ SUPPORT FOR
MATRIX2D
Class Name: Nails
Method Name: bestPath
Parameters: Matrix2D
Returns: int
Joe walks on nails as a hobby. Stepping on a lot of nails is much less painful
then stepping on few nails, and Joe wants to find the least painful path.
Joe's nail-boards can be broken down into grids. Conveniently, Joe has only 1
foot, and it is square. Further, his foot is exactly the size of one square in
a grid and when he takes steps, he hops into exactly and completely one square.
The square he hops into is always in front of him 1 square, in front of him 1
square & left 1 square, or in front of him 1 square & right 1 square.
Joe's nail-boards can be represented by Matrix2D's (see below for a description
of the Matrix2D class). Each element (row,column) in the Matrix2D represents a
square in the grid and contains an Object that is an instance of an Integer
that is the number of nails in the square. Joe starts at any square in column
0 and ends in any square in the last column. Joe always moves from square
(a,b) to square (a,b+1), (a+1,b+1), or (a-1,b+1) as long as the move keeps him
on the board.
A good path across the nail-board has a high average number of nails per square
and a low deviation of nails per square.
Joe defines the best path across a nail-board as the path where
M = (total nails walked on) - 4*(Joe's Deviation)
is maximum.
Joe uses Joe's Deviation because his math isn't strong enough to understand
standard deviations. Joe's Deviation is the non-negative difference in number
of nails between the square he steps on with the most nails and the square he
steps on with the least nails.
Implement a method Nails, which contains a method bestPath. The method takes
as a parameter a Matrix2D representing one of Joe's nail-boards and returns an
int that is the M value of the best path across the board.
The method signature is:
public int bestPath(Matrix2D numNails);
numNails is a Matrix2D containing Integers between 0 and 10, inclusive.
Both the number of columns and rows in numNails are greater than 0 and less
than 10.
Note:
-The board is coated with hydrochloric acid so stepping on a square with no
nails is even worse than stepping on a square with only 1 nail. However he
will step on a square with no nails if it maximizes M and a square with no
nails does not change the calculation of M.
-The solution must run in under 6 seconds.
Examples:
-If numNails = [[8,4,3,0][2,7,6,0][3,9,7,8][6,2,1,0]] the best path is (0,0) ->
(1,1) -> (2,2) -> (2,3) and the method should return M = 8+7+7+8-4(8-7) = 26.
-If numNails = [[10,10,10,0][0,0,0,0][5,5,5,5]], the best path is (2,0) ->
(2,1) -> (2,2) -> (2,3) and the method should return 20.
Matrix2D is a TopCoder developed class to represent a 2-dimensional matrix of
Objects. The matrix has r rows, numbered 0 to r-1, and c columns, numbered 0
to c-1.
To use Matrix2D, import tcclasses.Matrix2D.
The constructor takes two ints. The first is the number of rows in the matrix,
the second is the number of columns in the matrix. The constructor initializes
every element to "0".
The methods are:
void Matrix2D.set(int row,int col, Object element) sets the (row,col) spot in
the matrix to be element.
Object Matrix2D.get(int row, int col) returns an Object that is the element at
(row,col).
int Matrix2D.numRows() returns the number of rows in the matrix.
int Matrix2D.numCols() returns the number of columns in the matrix.
String Matrix2D.toString() returns a String representation of the matrix.
Object Matrix2D.clone() returns an Object that is a shallow copy of the matrix.