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
mit_gundigara:
20180813 08:17:06
what is the right answer for second test case?


roukaya_zaki:
20170806 16:49:30
sorry I got it


roukaya_zaki:
20170806 16:38:34
in the first case I think it should be 7 not 8


kshubham02:
20170121 10:59:35
Why is the tag dynamic programming? It can be solved using Dijkstra+Brute Force. 

praval_singhal:
20160602 10:32:24
Finally after so many silly mistakes Got AC :) 

Sandip Jana:
20160323 11:58:27
Learned a lot.. Thanku Problem Setter 

sai krishna:
20160303 18:32:13
How would be the answer for second case is 13 

Liquid_Science:
20160216 18:49:14
having a hard time in this,with java :( added to "to do"


baranowski:
20160108 18:28:54
JFCh! There is trailing whitespace in the input. 

sbansalcs:
20151028 14:58:12
1

Added by:  sieunhan 
Date:  20091129 
Time limit:  0.145s0.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 