DCEPC701  Amazing Maze
Chintu and his father Nikka, on their vacations, went to The Amazing Maze. But unfortunately, Chintu is has been separated from his father. His father Nikka has to find him as soon as possible in the maze or else Chintu will start crying soon.
The Amazing Maze is actually pretty amazing! The maze is built in a rectangular grid fashion. There are walls (#) and walking cells (.) in the grid. One can only walk through walking cells and so cannot jump off the wall. The amazing part is that each wall becomes a walking cell at some point of time (Neglect the transition time). Alternatively one can say that at some time t1 units, the wall will become walking cell and so one can step on to it at t1 time and at any time after t1. One can only move to adjacent walking cells from a walking cell. Adjacent cells mean the immediate up, down, right and left walking cells. It takes 1 unit of time to go from current cell to any adjacent cell. One can also wait on a particular walking cell for an adjacent wall to become a walking cell.
Nikka has the map of the maze with the information of the time at which the walls becomes walking cells. Also he knows at which walking cell he is situated and at which walking cell Chintu is situated. Help Nikka find out the minimum time required to reach to his son Chintu.
Input
First line contains T, the number of test cases.
Each case begins with two integers, M and N, the dimensions of maze.
Next contains M lines each containing N characters. Each character is either a “#” or a “.” as described above. This maze is the snapshot at time t=0.
Next M lines contain N space separated non negative integers. For each “.”, there will be a 0 and for each “#”, there will be a positive integer which represent the time at which that wall (#) will become a walkable cell.
Next line contains x1 and y1 denoting the position of Nikka in the maze.
Next line contains x2 and y2 denoting the position of Chintu in the maze.
Output
Output T lines each containing an integer, the minimum time required for Nikka to reach Chintu.
Constraints
1<=T<=10
1<=M<=200
1<=N<=200
0<=x1, x2<M
0<=y1, y2<N
For all #’s, time “t” will be > 0 and <= 10^4.
Example
Input:2
1 5
..#..
0 0 1 0 0
0 0
0 4
3 3
.##
##.
##.
0 1 2
3 4 0
6 7 0
0 0
2 2 Output: 4
4
hide comments
Simes:
20190913 15:59:14
Any chance Free Pascal or C# could be allowed?


thundercode:
20171002 17:04:29
100th ac :)


siddiboy:
20160415 21:42:21
Not really AMAZING... 

aditya730:
20160118 16:47:33
Not sure why people are getting WA due to a particular test case.Only trick in this question is to determine what will be the length of an edge connecting two particular nodes in the graph.The rest is implementing a standard algorithm.You can attempt SHOP which is based on a similar concept. 

Umair Khan:
20141020 08:01:35
Dafuq is wrong with the 5th test case. _ 

Petar Bosnjak:
20140703 00:10:41
not really an amazing maze, just a simple one 

saravanan:
20140603 07:36:21
wa in fifth test case


AVOID:
20140331 19:20:00
i also tle on 5th test case


Shaka Shadows:
20130710 14:26:00
@All: I guess there is no weird data in any test case, but all those ones failing at 5th test case probably have the same problem. The only remarkable thing here is, in my opinion, that your algorithm should not start with 0 for starting cell at certain cases, but those cases are not present according to the problem description. Last edit: 20130710 14:41:07 

Ujjwal Arora:
20130327 13:48:48
Getting TLE on 5th test case

Added by:  dce coders 
Date:  20120430 
Time limit:  0.453s 
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 