DWITE Online Computer Programming Contest, November 2009, Problem 5

Having returned to the crazy house from December 2007, this time we just want to know how well we can move between the rooms connected by Portals.

The input will contain two lines with one integer value each, ~R, C~ ~(0 \le R, C \le 20)~, representing the number of Rows and Columns that make up the floor plan. Followed by ~R~ lines, showing the floor plan layout, where:

• # - wall
• . - open space
• {a-j, A-J} - marking entrance and exit nodes of portals
• {1-5} - integers 1 to 5, marking points of interest

Lowercase letters mark entrance nodes, while corresponding capital letters mark exit nodes. That is, one can enter at point j and exit at point J. There will be no more than ~10~ portals in the floor plan.

The goal is to figure out which of the points are reachable, when starting from each of the 5 marked points.

The output will contain 5 lines. The first line corresponds to starting from point 1, second line from point 2, etc. The line will begin with the corresponding start node and a colon, followed by a set of integers, separated by a single space, in ascending order – other points of interest reachable from the starting point. If no other point is reachable, the output line is just n:, with no trailing spaces.

Note: Portals could create loops. In the sample below, room 1 leads to room 2, and room 2 has a path back to room 1. Please take care to avoid infinite loops, as those take a long time to execute.

Sample Input

10
11
..#.1..F#Af
..#.ea..#.2
###########
5.b.#BE#..4
....#c3#.C.
###########
.........#.
.d...D...#.
##########.
...........

Sample Output

1:2 3 4
2:1 3 4
3:4
4:
5:3 4

Problem Resource: DWITE