South Central USA Regional Programming Contest The Door/Key Problem
Results    Final Standings    Problem Set    Local Contest    Home    Schedule    Information    Details    FAQ    Contest Details    Welcome    Rules    Hints    Environment    Compile Howto    PC^2    About PC^2    Documentation    ACM    Intl Prog Contest    South Central US Regional    Registration		Introduction: 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 (room 0). Input: 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 sets. 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: 3A and the line for room 3 would read: 5F 7PX 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: END After the last data set, there will be a single line: ENDOFINPUT Notes: 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. Output: 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: YES Otherwise, print a line: NO Sample Input: START 1 2 1A A END START 1 5 1F 2A 2B 3CD 3E B C D F A E END START 1 10 9I 2A 3B 4C 5D 6E 7F 8G 9H A B C D E F G H X END ENDOFINPUT Sample Output: YES YES NO		[Printable]    LSU    Home    Search    Campus Map    ACM Chapter    Computer Science    Computng Services    Our Contests    2003    2002    2001    2000    Index