DCEPC701 - Amazing Maze

no tags 

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: 2019-09-13 15:59:14

Any chance Free Pascal or C# could be allowed?

edit: Nevermind, I figured out some C++.

Last edit: 2019-09-14 21:46:08
thundercode: 2017-10-02 17:04:29

100th ac :)

siddiboy: 2016-04-15 21:42:21

Not really AMAZING...

aditya730: 2016-01-18 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: 2014-10-20 08:01:35

Dafuq is wrong with the 5th test case. -_-

Petar Bosnjak: 2014-07-03 00:10:41

not really an amazing maze, just a simple one

saravanan: 2014-06-03 07:36:21

wa in fifth test case
:(

AVOID: 2014-03-31 19:20:00

i also tle on 5th test case

Shaka Shadows: 2013-07-10 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: 2013-07-10 14:41:07
Ujjwal Arora: 2013-03-27 13:48:48

Getting TLE on 5th test case
please reveal this mystery of 5th case
id : 8983095


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