MAWORK  Men at work
Every morning you have to drive to your workplace. Unfortunately, roads are under constant repair. Fortunately, administration is aware that this may cause trouble and they enforce a strict rule on roadblocks: roads must be blocked only half of the time. However, contractors are free to schedule their working hours, still they must follow regulations:
 Working periods (when the road is blocked) and rest periods (when the road is open) must alternate and be of fixed length.
 The beginning of the day (time zero) must coincide with the beginning of a period.
Write a program that, given a description of the road network and of contractors schedules outputs the minimal time needed to drive from home to work.
Input
The first line of the input contains a number T ≤ 10 that indicates the number of test cases to follow. The road network is represented on a N x N grid and the first line of each test case consists in the number N, 2 ≤ N ≤ 25.
Then follows N lines of N characters that represent the road network at time zero. Those lines are made of "." (standing for open road) and "*" (standing for roadblock) and they encode the rows of the grid in increasing order, while columns are also presented in increasing order. Conventionally, your home is at the position first row, first column, while your workplace is at the position last row, last column. Furthermore, you leave home at time t=0, that is, your starting position is first row, first column at time zero.
At a given time t, your car must be on some "open road" cell. It takes one time unit to drive to any of the four adjacent cells heading toward north, south, west or east, and you may also choose to stay on the same cell for one time unit. Of course, those five moves are valid if and only if the target cell exists and is free at time t+1.
Finally comes N lines of N characters that represent the contractors schedules. Those lines match the ones of the grid description and are made of N characters 0,1,...,9 that specify the duration of the working (and rest) period for a given cell. Observe that 0 is a bit special, since it means that the corresponding cell status does not change.
Output
The output consist in a single line for each test case, holding either the requested time, or NO, if driving from home to work is not possible.
Example
Input:
2 10 .********* ........** *.******.* *.******.* *.******.* *........* *.******.* *.******.* *........* ********.. 0000000000 0000000000 0000000000 0000000000 0000000000 0123456780 0000000000 0000000000 0123456780 0000000000 3 ... **. **. 021 002 000
Output:
34 NO
hide comments
lord voldemort:
20150228 00:06:18
data set is very weak


HM Mehrab:
20141008 10:15:01
Actually, brianfry713 from UVa made that test case, not me. 

LeppyR64:
20140506 15:10:44
Oh boy. HM Mehrab's test case helped a lot. I didn't realize that the roadblocks ('*') could change to open road ('.'). 

HM Mehrab:
20140501 07:47:51
Dataset is weak. For the following case, correct output should be 19, but my code outputs 20 and still got AC.


Aswin Akhilesh:
20111104 14:57:57
Phew! Gotcha! Last edit: 20120413 00:00:29 
Added by:  Adrian Kuegel 
Date:  20040716 
Time limit:  9s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  ACM Southwestern European Regional Contest, Paris 2003 