Yuvraj and Game
All submissions for this problem are available.
Yuvraj loves cricket and regularly plays with his friends but yesterday, one of his legs got fractured and now he is not able to go out and play. So, he decided to play an android game similar to cricket but this game is a little different from what the actual game is. In this game, there is an N*M matrix(field) and some players are randomly standing in the matrix to block the ball and stop the game. The ball starts to move from the first row and it can move either diagonally or vertically in the next row. Any movement in the same row or to the previous row is restricted. Considering the distance between any two rows as one unit, Yuvraj has to tell the maximum number of units (vertical row-wise distance) the ball can travel.
For example let # be the players and 0 be free path in the below matrix :-
0 # 0 0
0 # # #
# 0 # #
0 # # #
# # 0 #
In this matrix, a player starting from first row first column can at maximum, go upto 4 rows.
First line contains T, the number of test cases.
For each test case, first line contains number of rows N, number of columns M.
Next line contains number of players K.
Next K lines contain the coordinates of the form (a,b) at which the players are standing.
For each test case, print the correct answer given by Yuvraj in new line.
Input: 2 2 2 2 1 1 1 2 5 3 9 1 1 1 3 2 1 2 2 3 3 4 2 5 1 5 2 5 3
Output: 0 4
|Tags||algophobic, alph2016, daga_07, dynamic-programming|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, 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, SCM chicken, CLOJ, FS|
Fetching successful submissions