SPOJ.com - Problem BAT4

BAT4 - BATMAN4

Batman: "A hero can be anyone. Even a man doing something as simple and reassuring as putting a coat around a little boy's shoulder to let him know that the world hadn't ended."

THE BOMB IS TRIGGERED !!, IT WOULD BLOW UP IN A FEW MINUTES !!

BATMAN resorts to his BAT and decides to head towards the ocean with the bomb.

However in front of him lies a huge grid of tall buildings. Starting from the top-leftmost grid he needs to move to the bottom right-most grid to reach the ocean. Since the fuel of BAT has nearly exhausted, BATMAN decides to chose a path where the maximum up distance travelled at a time is minimized. However, each movement of the BAT up or down the building takes one unit of time. (Horizontal movements can be made in no time). The clock keeps ticking, So BATMAN decides to choose a path reaching the destination minimizing the maximum up distance and with as much time left as possible.

Every Hero Has a Journey. Every Journey Has an End !

CatWoman : "You don't owe these people anymore. You've given them everything."
BatMan : "Not everything, not yet."

NOTES :

BatMan requires to take the first jump on (1, 1)
Print NO is no time is left.
Minimum max up-distance is the first priority.

Input

The first line contains T, the number of test cases.

In each test case, the first line contains N (the size of the grid) and M (the time left).

The next N lines contain N integers, denoting the heights of the building.

Output

If BATMAN could reach the destination, print "YES", the maximum up distance travelled and the maximum time left with BATMAN.

If he could not reach the destination within time, print "NO".

Constraints

1 ≤ N ≤ 20

1 ≤ M ≤ 100

Example

Input:
1
3 40
2 4 3
4 5 3
2 4 6

Output:
YES : 2 32

Submit solution!

Added by:	Romal Thoppilan
Date:	2013-02-06
Time limit:	1s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: ASM64
Resource:	own problem

hide comments

2013-08-06 14:15:39 Eric Budiman Gosno
Is Batman can only move to right(i+1,j) and down(i,j+1)?
if batman can move to left and up also,I think your test case doesn't handle case when batman must take right then left to find better maximum up distance

since I only use right and down solution and got accepted

Last edit: 2013-08-06 14:21:59

2013-06-24 13:43:23 Ujjwal Arora
can batman move from (i,j) to (i+1,j+1)

or

only to (i,j+1) and (i+1,j)

edit : AC with considering only (i,j+1) and (i+1,j)

Last edit: 2013-06-24 14:16:03

2013-02-09 19:44:56 Romal Thoppilan
@:D -> your output formatting is wrong
Print a space after YES and before :
Other updates are done.

2013-02-09 19:44:56 :D
Hiding it for now. Not saying my solution is correct, but I really want you to check the problem and answer my questions below before I go to debug.

2013-02-09 19:44:56 :D
Please add an information that you need to jump to (1,1). So you actually start from field at level 0 next to (1,1)? Should we also add it to maximum up distance?

Also, what are the priorities? I think we are looking for the minimum maximum up distance, without going through time limit. Maximum time left is the second criteria. Is that right, because it's also not clear.

Shouldn't it be: "However , each movement of the BAT up or down the building takes one unit of time PER UNIT OF HEIGHT DIFFERENCE."

Finally, is time left 0 a valid "YES" case?

Last edit: 2013-02-09 14:38:33

2013-02-09 19:44:56 Romal Thoppilan
Yes your path is correct . But the time to jump (1,1) is also taken into account so 32

2013-02-09 19:44:56 Romal Thoppilan
Path chosen => (1,1)->(1,2)->(2,2)->(3,2)->(3,3)

Last edit: 2013-02-08 09:11:07