ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

Ural Championship 2005 Round II

About     Problems     Submit solution     Judge status     Standings
Contest is over

H. Top Secret

Time limit: 2.0 second
Memory limit: 64 MB
In the top secret district of the top secret city, there is a top secret factory which produces top secret Secrets. The top secret spy satellite, equipped with top secret imaging devices, took some top secret photographs. You have to interpret the photograph correctly. This is crucial for success of the top secret mission involving covert manipulation of potential enemy's Secrets.
The photo is repesented by a W × H matrix of cells, each cell containing one of the symbols:
.Empty, passable section
-Horizontal impassable barrier (wall)
|Vertical impassable barrier (wall)
+Impassable junction of horizontal and vertical walls
#The Secret
The Secret is a regular junction (+) with one of the objects of special interest contained inside. This object of interest is accessible from any of the four sides of the junction.
Unfortunately, secret agents are unable to penetrate walls, nor they are allowed to break them. But this is the only limitation — they are secret agents, after all.
We'll give a set of examples to clarify the agents' possibilities.
+-+-+ |-+-|
|#|#| |#|#|
+---+ +-+-+
In the first example the agent can walk freely from one Secret to another through a hole between the bottom horizontal and middle vertical walls. In the second example the hole is sealed by the junction. Agents can't use holes in the top wall — leaving the photographed area poses a huge risk to the mission. For the sake of simplicity, you can assume that the photographed area is surrounded with the barrier of "+"-es.
+-+...+-+ +-+...+-+
|#+---+#| |#+-+-+#|
+---+---+ +---+---+
Similarly, in the first example Secrets are connected, and in the second they are not.
+-----+ +++++++
+#####+ +#####+
+++++++ +++++++
If you remember that the Secret is a special case of junction, it will become clear why all the secrets in the first example are connected and why every secret in the second example is connected only with its neighbors.
Your task is to construct the secret connectedness graph. That is, the graph which set of vertices is the set of all secrets and the edge (a, b) exists if and only if it is possible for an agent to get from Secret a to Secret b without breaking the walls and leaving the area.
The dimensions of the photograph don't exceed 1000 × 1000 cells. It is known that there are no more than 100 Secrets on the photograph.


Input stream format is rather simple: it contains H lines, and each line contains a string W symbols long. These strings of symbols dene the secret photograph of size W × H.


Output the incidency matrix of the secret connectedness graph. Secrets are enumerated from top to bottom, from right to left. The matrix element in the ith row and in the jth column is 1, if ith and jth secrets are connected, and 0 otherwise.


Problem Author: Pavel Egorov
Problem Source: IX Collegiate Students Urals Programming Contest. Yekaterinburg, April 19-24, 2005
To submit the solution for this problem go to the Problem set: 1367. Top Secret