Chef and Telephone Network
All submissions for this problem are available.Chef is an employee in BSNL. He is the area manager, who checks for the internet connectivity issue in his area. Due to some violence in Lucknow, Internet connection has been stopped in the city. Only BSNL's internet is working in the city. A lot of new BSNL connection is now in demand in Lucknow. So, work loads increases on Chef. Each day Chef got a task to connect a new Internet network Cable from city A to city B via.poles. And if already that pole is occupied by any other service provider then Chef cann't use that pole. So, there $N$ cities each having $M$ poles. Chef has to start from a particular pole whose value is $S$ and connect the cable till pole whose value is $D$. If the value of a pole is '$x$', means that pole is already occupied. Chef is an honest employee of BSNL, so he want to use minimum poles for the connection. Help Chef in finding out minimum number of poles he can use , to connect cable from pole value $S$ to pole value $D$. If he can connect cable from current pole to any pole adjacent to it (except diagonal poles). ###Input: - First line will contain $T$, number of testcases. Then the testcases follow. - First line of test case, consist of two integers $N, M$ denoting cities and number of poles in each city. - Next $N*M$ line consists of value of the poles. ###Output: For each testcase, output in a single line answer given by minimum number of poles required. ###Constraints - $1 \leq T \leq 100$ - $2 \leq N,M \leq 10^3$ ###Sample Input: 1 3 3 x . D . . x S . x ###Sample Output: 4 ###EXPLANATION: Source pole is (2,0), destination pole is (0,2). Chef can use poles - (2,0)->(1,0)->(1,1)->(0,1)->(0,2). Hence the answer is 4.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, SQL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.