Max Gold :
Difficulty Level : Hard
Submissions : 527
Asked In :
Marks :100
: 2 | : 6
In a gold mine grid of size M*N, each cell in this mine has an integer representing the amount of gold in that cell, 0 if it is empty.
Return the maximum amount of gold you can collect under the following conditions:
Every time you are located in a cell you will collect all the gold in that cell.
You can walk one step from your position to the left right up or down.
You can't visit the same cell more than once.
Never visit the cell with 0 Gold.
You can start and stop collecting gold from any position in the grid that has some gold.
The first line of input contains two integers M, N the number of rows and columns in the matrix ($$$1 \le M, N \le 15$$$).
Next M*N line contains the element of the matrix.
For each test case print, the maximum amount of gold u can collect
3 3 1 0 0 0 44 0 0 0 12
44
The Number of cells that contain gold is less than 25.
