The Door/Key Problem
Time Limit: 2 Seconds
Memory Limit: 65536 KB
Thibodeaux has managed to once again lock himself inside his own house (this
happens all too often). Boudreaux, being the good buddy that he is, has taken
the precaution of scattering keys to the locked rooms throughout Thibodeaux's
house. It is up to you to determine if Thibodeaux can make it to his bedroom
Input to this problem will consist of a (non-empty) series of up to
100 data sets. Each data set will be formatted according to the
following description, and there will be no blank lines separating data
A single data set has 4 components:
Start line - A single line:
START M N
where M indicates the starting room, and N indicates the
number of rooms in the house (1 ≤ N ≤ 20).
Room list - A series of N lines. Each line lists, for a
single room, every door that leads to a room of higher number and the keys
necessary to open the door from either side. Rooms will be represented by
numbers and each key will be represented by a single capital letter
(A - Z). For example, if room 3 had doors to rooms
1, 5, and 7, and the door to room 1
took an A key, the door to room 5 took an F
key, and the door to room 7 took an X key and a
P key, the line for room 1 would read:
and the line for room 3 would read:
The first line in the list represents room 0. The second line
represents room 1, and so on until the last line, which
represents room N - 1. It is possible for lines to be empty
(in particular, the last line will always be empty since it is the highest
numbered room). On each line, the adjacent rooms are always listed in
ascending order. It is possible for rooms to be connected by multiple
doors and for doors to require multiple keys; required keys for a door
will be listed in alphabetical order.
Key list - A series of N lines. Each line lists, for a
single room, the keys, in alphabetical order, that are in that room.
End line - A single line:
After the last data set, there will be a single line:
There will be no more than 100 doors in any data set.
No room will have more than 20 doors.
Some doors may not require keys.
In any data set, all keys are unique and can be used multiple times.
For each data set, there will be exactly one line of output. If it is possible
for Thibodeaux to reach his bedroom (room 0), print a line:
Otherwise, print a line:
START 1 2
START 1 5
2A 2B 3CD 3E
START 1 10
Source: South Central USA 2003