DP - Deliver pizza


Tom McCoffee owns the only pizza delivery place in the mountains. The terrain is represented as a rectangular grid of squares, where each square either contains a building or is empty. Each empty square has an integer height between 0 and 9, inclusive. Today, each building in the area has ordered one pizza, and Tom must use his two delivery boys to fulfill all the orders in the shortest total amount of time possible.


From each square in the grid, you can only move to adjacent squares. Two squares are adjacent if they share an edge. You can only move between two empty squares if the absolute difference of their heights is less than or equal to 1. If the height difference is 0, it takes 1 minute to make the move, and if the absolute height difference is 1, it takes 3 minutes.

You can always move to a building from any of its adjacent squares and vice versa, regardless of height. This is because all buildings are taller than the highest terrain, and each building has entrances and exits for all its adjacent squares at the correct heights. Moving to or from a square containing a building takes 2 minutes. The delivery boys are allowed to enter buildings even if they are not their final destinations. Note that the pizza place itself is also a building.


Each delivery boy can only carry one pizza at a time. This means that after each delivery, the delivery boy must return to the pizza place to pick up another pizza if there are more deliveries left to do.


Your task is to print the minimum time in minutes at which the last delivery can be made. If it is not possible to deliver all the pizzas, print -1 instead.


Input
One line containing an integer C, the number of test cases in the input.
For each of the C test cases:
• The first line consists of M and N the size of the grid. M is the number of rows and N is
the number of columns.
• The next M lines consists of a string which length is N. Each character could be ‘$’, ‘X’
or digits from ‘0’ to ‘9’. '$' represents a building from which a pizza was ordered, 'X'
represents the location of the restaurant, and the digits '0'-'9' represent the heights of
empty squares.


Output
For each test case, print the minimum time in minutes at which the last delivery can be made. If
it is not possible to deliver all the pizzas, print -1 instead.


Limits
1 <= C <= 30
1 <= M <= 50
1 <= N <= 50
There are at most 20 buildings.

Sample input
2
3 7
3442211
34$221X
3442211
3 7
001000$
$010X0$
0010000


Sample output
8
13


hide comments
roukaya_zaki: 2017-08-06 16:49:30

sorry I got it

roukaya_zaki: 2017-08-06 16:38:34

in the first case I think it should be 7 not 8

kshubham02: 2017-01-21 10:59:35

Why is the tag dynamic programming? It can be solved using Dijkstra+Brute Force.

praval_singhal: 2016-06-02 10:32:24

Finally after so many silly mistakes Got AC :)

Sandip Jana: 2016-03-23 11:58:27

Learned a lot.. Thanku Problem Setter

sai krishna: 2016-03-03 18:32:13

How would be the answer for second case is 13

Liquid_Science: 2016-02-16 18:49:14

having a hard time in this,with java :( added to "to do"

Edit : Did it ,seemed i had a problem with my subset sum algorithm

Last edit: 2016-02-17 06:56:48
baranowski: 2016-01-08 18:28:54

JFCh! There is trailing whitespace in the input.

sbansalcs: 2015-10-28 14:58:12

1
3 3
$X$
$$$
$$$
What should be the output for this?
According to SPOJ toolkit it should be 26. But according to me it should be 24.

dvmxlador_47: 2015-10-25 14:05:33

In the second test case the distnace from x to $ is 2+3+3+2 =10 how come it be 13.Pls Explain
0 0 1 0 0 0 $ // 2 3 3 2
$ 0 1 0 X 0 $ // $ 0 1 0 X
0 0 1 0 0 0 0


Added by:sieunhan
Date:2009-11-29
Time limit:0.145s-0.774s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 NODEJS OBJC PERL6 SQLITE VB.NET
Resource:Topcoder - ACM Vietnam Practice