Journey to the New World
All submissions for this problem are available.
Straw Hat Pirates have just reached the Grand Line. Their next destination is the New World.
The islands are in a form of matrix.
G I I I … I
I I I I … I
I I I I … N
Here G is the Grand Line, I are the islands and N is the New world.
Every Island has a Marine Base and every Marine Base has certain number of marines. Straw Hat’s don’t want to cause a lot of commotion so he wants to face the least number of marines. They can go to the islands on the right, left, up or down of the current island. Help Straw Hat’s find the optimal path.
The first line of the test case contains a single integer M, denoting the size of matrix.
Next M lines contain M space separated integers Bi’s, denoting the number of marines in an island.
The first cell of the matrix has the value 0.
You have to output a single integer denoting the minimum number of marines that Straw Hat Pirates will have to face.
- 1 ≤ M ≤ 50
- 1 ≤ Bi ≤ 500
0 50 4 5 6
1 2 3 51 7
6 80 74 9 8
65 64 49 10 56
85 72 52 11 0
Example case 1. starting from cell (0,0), they go -> (1,0) -> (1,1) -> (1,2) -> (0,2) -> (0,3) -> (0,4) -> (1,4) -> (2,4) -> (2,3) -> (3,3) -> (4,3) -> (4,4)
On adding the values on those cells, 0+1+2+3+4+5+6+7+8+9+10+11+0=66.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, GO, PYP3|
Fetching successful submissions
If you are still having problems, see a sample solution here.