Just the distance
Deisy is working on a robotics project, she wants to test the robot at the top before sending it to a very important company, she made a complete map for the robot, the robot is in the beta test, so it's a little dummy, the robot can't walk in diagonals, it only can walk in four directions; north, south, east or west, Deisy thinks someway this is a very bad thing, so, she wants to know if a diagonal is always the best path for the robot to go through.
You are going to test the robot's diagonal steps versus the real steps the robot can make from a map A to a map B, having in consideration that the robot can start whenever in map A or B and arrives to the nearest point in B or A, also, Deisy can choose any point as a start for the robot (this point will belong to a map) and you must not compare the set of points where the robot belongs.
Definition of a "map": a map is a set of stars (*) in adjacency, we define the adjacency as the four positions (north,south,east,west), meaning that a star is adjacent to other if they are communicated by one of these positions.
INPUT:
The first line of input will contain an integer T denoting the T test cases, then, T cases will follow. Each of the following cases will contain a line with an integer N, then N lines with N characters each will follow, denoting the map the robot will have to traverse from a set of points A to a set of points B, a free space will be denoted by '-' and a occupied space by some point will be denoted by a character '*', it is guaranteed that there will be always two maps.
OUTPUT:
Output the string “Scenario #i: “ where i is the test case you are analyzing followed by the option to choose, output 1 if the robot can go by its normal direction, 0 if going in diagonals is better.
SAMPLE DATA:
|
INPUT |
OUTPUT |
|
2 5 ---** ---** ----- **--- **--- 4 *--* *--* *--* *--*
|
Scenario #1: 0 Scenario #2: 1 |
Explanation of the first case: For each point in the matrix either you start in map A or B, traversing in diagonals will always be better, the output should be zero (0).
Note: if Deisy find herself with equal distance between the diagonal and the "normal" steps of the robot, she will choose the "normal" steps as the best, in this case, the output should be 1 (normal is better).
CONSTRAINTS:
2<=N<=1000