Problem Statement |
| | You are trying to find a way around a maze which consists of a number of rooms, each of which may have doors open to other rooms that are only open at specific time periods. You will start in a certain room, at time = 0. At each time step, a set of doors will be open connecting various rooms to each other. However, the doors are all one-way, and allow passage in only one direction (though there may be two one-way doors between a pair of rooms so that you can go in either direction). Additionally, you have decided to move through a door every time step, so unless there is a door which connects a room to itself (which is possible) you must move to a new room at each time step. Only paths which move through a door at each time step are valid (see example 4).
At each time step, there will be a set of open doors which is represented by a single uppercase letter ('A'-'Z').
The maze will be represented by the input rooms, where each element of rooms tells you which doors leading out of a room are associated with which letters. Each element will be formatted as "<letter>:<adjacent room 1>,<adjacent room 2>,... <letter>:<adjacent room 1>,...". In other words, element i of rooms will be a space delimited list of the rooms that are reachable from room i via doors associated with a certain letter. Thus if
rooms = {"A:1 B:0,1","A:0"}
This means that for the letter 'A', you can get from room 1 to room 0, and from room 0 to room 1. For the letter 'B' you can get from room 0 to room 0 or from room 0 to room 1.
The second input, doors, represents which sets of doors are open at which time steps. So, if doors were "AB", then doors associated with the letter 'A' would be open at time step 0, and doors associated with 'B' would be open at time step 1. Thus, for the above example of rooms, if you started at room 1, there would be 2 possible paths with the same length as doors. You could go from room 1 to room 0 and then to room 0 again (signified "00"), or you could take the path "01".
The starting room will be denoted by the input start, which indicates that you should start in the room represented by the element start of rooms (indexed from 0). Your method should return a int[] representing which rooms can possibly be reached (at the final time step) by going through some door at each time step, and not skipping any time steps. The return should be sorted in ascending order. |
| |
Definition |
| | | Class: | Rooms | | Method: | finalRooms | | Parameters: | String[], String, int | | Returns: | int[] | | Method signature: | int[] finalRooms(String[] rooms, String doors, int start) | | (be sure your method is public) |
|
| |
|
| |
Notes |
| - | If an element of rooms does not contain some letter, this indicates that there are no doors coming out of this room associated with that letter. See example 4. |
| |
Constraints |
| - | Each element of rooms will be formatted as "<letter>:<adjacent room 1>,<adjacent room 2>,... <letter>:<adjacent room 1>,...". For each <letter> present in each element, there will always be at least one adjacent room associated with it. |
| - | No <letter> will be repeated in any element of rooms. |
| - | Each <letter> will be an uppercase letter ('A'-'Z'). |
| - | Each <adjacent room i> will be an integer between 0 and the number of elements in rooms-1, inclusive, with no extra leading zeros. And, for each letter, no room will be repeated. |
| - | rooms will contain between 1 and 50 elements, inclusive. |
| - | Each element of rooms will contain between 1 and 50 characters, inclusive. |
| - | doors will contain between 1 and 50 uppercase letters ('A'-'Z'), inclusive. |
| - | start will be between 0 and the number of elements in rooms-1, inclusive. |
| |
Examples |
| 0) | |
| | {"A:0 B:1","A:1 B:0"} | "AB" | 0 |
| Returns: { 1 } | | We start in room 0. During the first time step, the 'A' set of doors is open, so we can go from room 0 to room 0, since the first element of rooms has "A:0". That is our only option, so we go through the door to room 0. At time step 1, the 'B' set of doors is open, and the first element of rooms tells us that we can only go from room 0 to room 1 when the 'B' set of doors is open. So, after two time steps, the only option is to be in room 1. |
|
|
| 1) | |
| | {"A:1 B:0","A:0 B:1"} | "AABAAB" | 1 |
| Returns: { 1 } | |
|
| 2) | |
| | {"B:1 Z:0","B:0 Z:2","B:2 Z:1"} | "BBZZB" | 0 |
| Returns: { 1 } | |
|
| 3) | |
| | {"A:0,1,2,3","A:0,1,2,3","A:0,1,2,3","A:0,1,2,3"} | "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA" | 2 |
| Returns: { 0, 1, 2, 3 } | | Here we can get from any room to any other room when the 'A' set of doors is open. |
|
|
| 4) | |
| | {"D:0","D:0","D:0","D:0"} | "GDDDDD" | 3 |
| Returns: { } | |
|