How do I solve this linear Data Structure Implementation question? How would I s

Question

How do I solve this linear Data Structure Implementation question? How would I start? Given the starting point in a maze, you are to find and mark a path out of the maze which is represented by a 30x30 array of 1s (representing hedges) and 0s (representing the foot-paths). There is only one exit from the maze (represented by E). You may move vertically or horizontally in any direction that contains a 0; you may not move into a square with a 1. If you move into the square with an E, you have exited the maze. If you are in a square with 1s on three sides, you must go back the way you came and try another path. You may not move diagonally. For this program, use can ONLY use a single linked list.

Explanation / Answer

This is easily solved using a Depth first search.

//visited positions is a linked list

algorithm(maze, start, visited_positions):

   if maze[start] == 'E':
       print("PATH FOUND: ")
       print visited_positions
       exit("SUCCESSFUL")

   push_to_linked_list(visited_positions, start)
   for all neighbours of start:
      
       if neighbour is 0:
           if neighbour not in visited_positions:
               algorithm(maze, neighbour, visited_positions)

   exit("UNSUCCESSFUL")

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

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