All Submissions


Akshay has a lot of work to do this Bitotsav. So he asks god to create a copy of him for a day so that he can be present at 2 places at a time. God granted his wish.

The terrain of BIT 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, Akshay has atleast some work to do at each building in the area. Akshay 1 and Akshay 2 both want to complete all the jobs in shortest total amount of time possible. The main problem in BIT is the huge campus. It only takes time to go from here to there. The time to do the job can be ignored.

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 mins.You can always move to a building from any of its adjacent squares and vice-versa, regardless of height. This is because the core members always find some way out to do things faster. Moving to or from a square containing a building takes 2 minutes. Moving from one building to another also takes 2 minutes. Akshays are allowed to enter buildings even if they are not at their final destinations.

After each job Akshay completes, he must return to his room to know about the details of his next task. Note that boys hostel is also a building. Your task is to print the minimum time in mins in which the last job can be done and they return to their hostel. If it is not possible to do all the jobs, 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 rows and N 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 where Akshay has some work to do , 'X' represents the boys hostel 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 job is finished. If it is not possible to do all the jobs, print -1 instead.

Limits
1 <= C <= 500
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
16
20


Problem Setter : ACM Team

Languages: AWK,Bash,Brain,C,C++,Java,C#,JavaScript,Pascal,Perl,PHP,Python,Python3,Ruby,Text

Time Limit: 2 Second(s)
Score: 100 Point(s)
Input File Limit: 50000 Bytes

Submit

Login to post clarification.

No Clarifications.

Contest

Mode Judge

Passive

Online

Overall Rankings

RankNameScore
1xyz0
2Ams0
3TIP0
4team420
5xyzz0
6asdasdasd0
7abcd0
8khankhan0
9Gabriel0
10gigel0