As your reward for saving the Kingdom of Bigfunnia from the evil monster “Expone

Question

As your reward for saving the Kingdom of Bigfunnia from the evil monster “Exponential Asymptotic,” the king has given you the opportunity to earn a big reward. Behind the castle there is a maze, and along each corridor of the maze there is a bag of gold coins. The amount of gold in each bag varies. You will be given the opportunity to walk through the maze, picking up bags of gold. You may enter only through the door marked “ENTER” and exit through the door marked “EXIT.” (These are distinct doors.) While in the maze you may not retrace your steps. Each corridor of the maze has an arrow painted on the wall. You may only go down the corridor in the direction of the arrow. There is no way to traverse a “loop” in the maze. You will receive a map of the maze, including the amount of gold in and the direction of each corridor. Describe and analyze an efficient algorithm to help you pick up the most gold in this maze while traversing a path from the start to the finish.

NOTE: PLEASE DO NOT WRITE REAL CODE. PSEUDOCODE IS FINE. Also, please prove the running time of your algorithm.

Explanation / Answer

Use breadth first search algorithm.

paths = new queue()

highestmoney = 0

bestpath = new array()

queue.enqueue(ENTER)

while queue.length is more than 0

position = queue.dequeue()

money = 0

path = new queue()

path.enqueue(position)

while position is not EXIT:

if position has gold:

money = money + gold

if money > highestmoney:

highestmoney = money

bestpath = path

if position has multiple paths:

paths.enqueue(all paths except current)

position = position.next

return maxgold, bestpath

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

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