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 no. 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:4 41#...4 4 #... .2#. ..#3 1..#.2#...#31..#Output: 4
hide comments
ayush_1997:
20170621 21:15:49
100th :) 

Sushovan Sen:
20170508 07:47:03
1


conquistador:
20170115 13:15:00
the trick is to find where they can meet outside the grid 

gustavoaca1997:
20160830 08:19:37
got me AC while break of Night Swimmers by Foals was playing #Epic 

manhterry93:
20160728 04:07:36
BFS 3 times, AC in 1 Go..... Last edit: 20160728 04:07:56 

Oasis:
20151219 07:17:40
nice one..for those getting wa, try


anand pandey:
20150212 14:56:48
Nice one . 

krish:
20150123 19:46:00
good question... 

Deepak Gupta:
20141213 17:26:08
The given test case gets copied as:


Aditya Joshi:
20141012 08:28:22
@Ankit Jain: I don't know that particular case, but have you thought about the cases in which they meet outside the grid? 
Added by:  dce coders 
Date:  20120430 
Time limit:  0.419s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  ASM32GCC MAWK BC CCLANG C C++ 4.3.2 CPP CPP14 CPP14CLANG COBOL COFFEE DCLANG DDMD DART ELIXIR FANTOM FORTH GOSU GRV JAVA JSMONKEY KTLN NIM NODEJS OBJC OBJCCLANG OCT PICO PROLOG PYPY PY_NBC R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET 
Resource:  Own Problem 