DCEPC706 - Meeting For Party

Ankur, Anuja and Jyoti are planning to have party at some place. Their houses are located at different points in a rectangular grid of size M*N. They want to meet in minimum time and then party.

The M rows and N columns rectangular grid contains some impassable points (denoted by a #), however. So none of them wants to step over these points. They can only step over passable points (denoted by a .). They can also meet at some point outside the grid. You can assume that the points outside the grid are all passable. They cannot party on an impassable point and they have their house only on passable point. They can move either to North, South, East or West passable point from the current passable point and it takes 1 unit time to do so. Also they can wait at a passable point if they want to.

Find the minimum time of meeting.

Note: Assume that they will always meet at some point.

Input

First line gives T, the number of test cases.

Each test case has two space separated integers M and N, the dimensions of the grid.

Next M lines contain N characters per line (no spaces). Characters can be either “#” (impassable) or “.” (passable) or “1” (Ankur’s house) or “2” (Anuja’s House) or “3” (Jyoti’s house). Each test case will have exactly 1 “1”, exactly 1 “2” and exactly 1 “3”.

Output

Output T lines, each containing the required answer.

Constraints

1<=T<=10
1<=M<=200
1<=N<=200

Example

Input:
1
4 4
#...
.2#.
..#3
1..#

Output:
4

Added by:dce coders
Date:2012-04-30
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:ASM32-GCC MAWK BC C-CLANG C NCSHARP C++ 4.3.2 CPP CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JAVA JS-MONKEY JULIA KTLN NIM NODEJS OBJC OBJC-CLANG OCT PICO PROLOG PYPY PYPY3 PY_NBC R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET
Resource:Own Problem

hide comments
2017-06-21 21:15:49
100th :)
2017-05-08 07:47:03 Sushovan Sen
1
5 5
##.##
#.###
1.###
..##2
#.3.#
Is ouput 6 correct?
Re: YES

Last edit: 2017-05-09 08:55:00
2017-01-15 13:15:00
the trick is to find where they can meet outside the grid
2016-08-30 08:19:37
got me AC while break of Night Swimmers by Foals was playing #Epic
2016-07-28 04:07:36
BFS 3 times, AC in 1 Go.....

Last edit: 2016-07-28 04:07:56
2015-12-19 07:17:40 Oasis
nice one..for those getting wa, try
1
3 3
1#2
#.#
##3
ans is 4
2015-02-12 14:56:48 anand pandey
Nice one .
2015-01-23 19:46:00 krish
good question...
2014-12-13 17:26:08 Deepak Gupta
The given test case gets copied as:
1
#...
4 4
#...
.2#.
..#3
1..#
2014-10-12 08:28:22 Aditya Joshi
@Ankit Jain: I don't know that particular case, but have you thought about the cases in which they meet outside the grid?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.