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