Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|

Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |

Language: The Door/Key Problem
Description 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 Source |

[Submit] [Go Back] [Status] [Discuss]

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di

Any problem, Please Contact Administrator