1 \(s / 128\) \(MB / 120\) points

While surfing online, Slavko came across an ad displaying a system of containers and pipes

(an example of such system is illustrated in the image below) with the message: “If container

1 starts filling up with water, determine the order in which the containers get filled up.”

The system consists of \(K\) containers denoted with numbers from 1 to \(K\) , and we can describe

it using a matrix of characters with \(N\) rows and \(M\) columns. The containers are in the shape

of a rectangle , and the outlines of the containers and pipes are shown with the following

characters:
●
‘-’ if it’s a horizontal part of the outline,
●
‘|’ if it’s a vertical part of the outline, and
●
‘+’ if it’s a spot where the horizontal and vertical parts of the outline connect. An

exception is where the containers and pipes connect. In that case, the container

outline dominates (see sample tests).

In an arbitrary place within each container, there is a string of digits that represent the label

of the container, and all the other fields in the matrix are equal to ‘.’ (dot).

All containers except the one labeled with 1 have exactly one supply pipe that enters the

container in its upper side . The container labeled with 1 does not have a supply pipe.

The containers can have multiple (also possible, zero) discharge pipes that leave the

container out of its lateral side . The places where discharge pipes leave a container will be

in mutually distinct rows in the matrix.

The pipes directly connect two containers, which means that it is not possible to split the

pipes or connect multiple pipes into one, and no two pipes will intersect. On their way,

looking from the source to the destination container, the pipes always descend to the

following row or stay in the same row. In other words, they never go back to the previous

row, so the water can flow freely from one container to another.

The water enters a container until it is full. If the water level reaches the level of the

discharge pipe, the water will flow through that pipe until the container the pipe leads into is

filled up.

Help Slavko and determine the order in which the containers will fill up.

Please note :
●
The test data is such that each character ‘+’ is surrounded with exactly one

character ‘-’ to the left or the right side and exactly one character ‘|’ to the upper or

1 \(s / 128\) \(MB / 120\) points

lower side, and all other adjacent characters in directions up, down, left and right will

be equal to ‘.’ (dot).
●
The only places where the pipe in the matrix is in a field adjacent to the container

outline are the places where the pipe enters or exits the container. In other words, a

pipe will never run right next to a container (except where it connects with the

container). The entry for the supply pipe is labeled with the character ‘|’ above a

container, whereas the exit of the discharge pipe is labeled with the character ‘-’ on

the lateral side of a container.

In test cases worth 70% of total points, it will hold \(N\) , \(M\) ≤ 100.

1 \(s / 128\) \(MB / 120\) points

The first line contains two integers \(N\) and \(M\) (1 ≤ \(N\) , \(M\) ≤ 1000), matrix dimensions.
The following \(N\) lines contain \(M\) characters describing the container system.

You must output \(K\) lines. The \(i\) ^{th} line contains the label of the container that fills up \(i\) ^{th}{ }. A

solution will always exist and will be unique.

생성자가 기록되지 않았습니다.

출처 COCI 2017/2018 Contest 7