DWITE '09 R2 #5 - Portals Redux

View as PDF

Submit solution

Points: 8
Time limit: 1.0s
Memory limit: 64M

Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig
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 \leq R, C \leq 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

Lower case 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 out 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 the "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

Attribution-NonCommercial-ShareAlike 3.0 Unported (CC BY-NC-SA 3.0) Problem Resource: DWITE


Comments

There are no comments at the moment.