시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 26 | 11 | 10 | 45.455% |
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:
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 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 ith line contains the label of the container that fills up ith. A solution will always exist and will be unique.
12 13 ..+--+....... +-|..|....... |.|.1|--+.... |.+--+..|.... |......+----+ +---+..|..2.| ....|..+----+ .+--+........ .|........... +---+........ |.3.|........ +---+........
2 3 1
8 10 .......... .......+-+ ...+---|1| ...|...+-+ ...|...... ..+-+..... ..|2|..... ..+-+.....
2 1
Clarification of the first test case:
Container 1 starts filling up with water.
The water level in container 1 grows, and in one moment reaches the level of the discharge pipe leading to container 2. The water flows through the pipe until container 2 fills up.
After that, the water level in container 1 keeps growing until it reaches the level of the discharge pipe leading to container 3, which fills up next.
Finally, the water level in container 1 keeps growing and the container fills up.