Graph Algorithms. You are playing a game where there is a monster chasing you in
ID: 3771153 • Letter: G
Question
Graph Algorithms. You are playing a game where there is a monster chasing you in a maze. The maze has a graph structure, possibly with cycles. Your goal is to escape from the maze before the monster catches you and eats you. You know the following: the maze layout, your location in the maze, and the monster's location However, the escape door is invisible unless you are right in front of it. You and the monster alternate moves. At each move, the player moving (you or the monster) must move to a node adjacent to the mover's current position in the maze.Explanation / Answer
Key points to note to save you from the monster,
Key algorithm to use in this case is Breath First Search (BFS) algorithm approach.
The advantage BFS is that as we traverse the graph all nodes (here locations) are processed in the order of adjasent nodes from the current node and so on. This is like taking one step from your current position in the maze. To solve this problem we have do a BFS from monster's location and your location with a little book keeping. Below is how i would approach the solution.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.