SPOJ.com - Problem RPLJ

RPLJ - 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

INPUT
2
5
---**
---**
-----
**---
**---
4
*--*
*--*
*--*
*--*

OUTPUT
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

Submit solution!

Added by:	david_8k
Date:	2012-05-05
Time limit:	0.106s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: ASM64
Resource:	Own Problem used for the RPL contest

hide comments



2021-01-23 08:43:20 Horrible, unintelligible statement and full retard TL. In example given by psetter below, the 2 points in the left area he refers to cannot be used to reach the other area diagonally at all. Hence, min_diag_dist is the minimum distance between any two points in distinct areas on the same diagonal, and min_norm_dist is one between any two points in distinct areas using normal NESW traversal. This gets WA as well as measuring for every starting point separately and every other interpretation I could come up with. When one of the approaches got me TLE, spent some extra time to translate to C in order to fit in this idiotic limit, but got WA too. Bloody waste of time :(
2012-12-27 03:53:00 Afrizal if we compare the distance between normal and diagonal, is there must be come from same start point?
2012-05-14 17:14:48 :D Ok, so correct me if got anything wrong: A sum of of maps A and B is a set of all valid start points. For each of this points we count the "normal distance" and "diagonal distance" to the closest point of the opposite map. If for any of those points dNormal<=dDiag the answer is 1, otherwise 0.
2012-05-14 13:43:33 david_8k @:D For diagonals, you just "move" to diagonals steps. (not the whole 8 directions). The answer is 1 if exists at least one point that the Normal_Distance is less or equal than Diagonal_Distance, correct. I couldn't understand your final question... This is what I understood 3 - - *-- Imagine that map A is the set {(1,1),(2,1),(3,1)} and the map B is the set {(1,3),(2,3)} You can start from any point in A going to the nearest point in B, as you can see, two of three points arrives from A to B using "normal distance", however, you just need one, as you can choose where is going to begin the robot... Conveniently, is better that the robot start in any point of A that takes the robot to B in the normal distance if possible.
2012-05-14 07:35:07 :D For diagonal can you move only in diagonal or in all 8 directions? Is the answer 1, if there exists AT LEAST one start point for witch dNormal<=dDiag? You can move form interior points of map as well right? for example in first test case, are points (0,4) and (4,0) valid start points?