All submissions for this problem are available.
Dexter, is very fond of playing puzzle games. In
one such game he encounters, he has to help his
character DiDi to move through a checkerboard
and reach the other end. The checker board
contains R(1<=R<=100) rows and C(1<=C<=100)
columns. Every square DiDi steps on, she loses
some health H(1<=H<=100). Each suware is assigned a certain
health that DiDi loses, and this value may or may not be same
for all squares. The objective of the game is to
start from any square in the first row and reach any element in the Rth row
by losing minimum amount of health. DiDi is
programmed in such a way that she can move only
in the forward direction, that is, straight,
diagonally left or diagonally right(total of 3
different moves are possible). Can you help Dexter
with winning this new game he has come
Also denote the path which is traversed by DiDi. (It is given that the input data does not give two paths resulting in minimum loss of health).
First line contains number of test cases T
(1<=T<=100), which is followed by the inputs
for each test case. For each test case, first
line consists of R and C, followed by a RxC
matrix denoting the health lost for each
Output contains 2T lines, 2 for each of the T
test cases. Of these 2 lines, the first denotes
the amount of minimum health lost. The second
denotes the column number that DiDi is present in with
each step she takes.
Note: R, C, T, H are all integer
Input: 2 2 3 24 75 19 76 51 91 4 4 1 2 80 99 90 75 86 3 94 88 96 4 60 70 75 5 Output: 70 3 2 92 3 4 4 4
The above example has 2 test cases. In the first test case the checkerboard has 2 rows and 3 columns. Its corresponding output mentions that the total health lost is 70. The next line indicates that when DiDi is in the first row, she is in the 3rd column and when she is the second row, she is in the 2nd column. And similarly for the next test case, total health lost is 92. And with the four steps DiDi takes, she moves in the columns 3, 4, 4 and 4 respectively.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.