You just started working in a new building. One of your new co-workers tells you

Question

You just started working in a new building. One of your new co-workers tells you that many people have trouble getting locked out of their work areas because many of the doors only open from one side. Your co-worker decides to help you out by giving you a list of all the rooms in the building, and next to each room is a list off all the doors in the room that can be opened from that room. Let D be the number of doors in the building and R be the number of rooms. Given an O(R + D) time algorithm to produce the list of rooms which you can travel to without getting locked out of your office.

NOTE: The answer does not need to be coded in any language or pseudocode, just give a step-by-step algorithm in english of how to achieve this so that I may be able to understand it.

Explanation / Answer

Below is explanation of algorithm :

We assume that person is in a particular room and then start looking for door list. if a door opens then we will check if its a exit door. if its not a exit door then we will check if there is a door to any other room. if There is no door then we will come back to previous room. If there is a door then we will continue searching setting the person to be in Rcurrent untill we find exit Door.

1. Let P be the person standing in Room Ri

2. Check Doors List.

3. if RiDj opens

4. check if its the Exit(Door)

5. if there is no Door D for any other room then go to previous room R else continue to step 6.

6. else set as Person in Rcurrent. Repeat from step 2 to step 5 untill exit door.

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.