A number maze is an n Times n grid of positive integers. A token starts in the u

Question

A number maze is an n Times n grid of positive integers. A token starts in the upper left corner; your goal is to move the token to the lower-right corner. On each turn, you are allowed to move the token up, down, left, or right; the distance you may move the token is determined by the number on its current square. For example, if the token is on a square labeled 3, then you may move the token three steps up, three steps down, three steps left, or three steps right. However, you are never allowed to move the token off the edge of the board. Describe and analyze an efficient algorithm that either returns the minimum number of moves required to solve a given number maze, or correctly reports that the maze has no solution.

Explanation / Answer

Assume A[1…n, 1…n] as input maze.

Construct a directed graph in which each vertex correspond to a cell in the grid and each edge represent a valid move, which is either left, right, up or down.

Every Sequence of legitimate move in A corresponds to directed path in G.

To find out the total moves, a shortest path has to be calculated form (1,1) to (n,n) in G.

Therefore shortest path can be calculated using Breadth First Search in O(V+E)=O(n2)

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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