You are in a maze represented by a rectangular grid. One cell is the start cell,...

 

Transcribed Image Text:

You are in a maze represented by a rectangular grid. One cell is the start cell, another is the cell you want to get to. Some pairs of adjacent cells have a wall between them, preventing you from moving directly from one to the other. There is at least one path from the start to the end. Suppose that the characters U, D, L, R. represent moving up, down, left and right by one grid cell. A string of these characters represents a sequence of movements through the maze, but is only valid if it does not make you bump into a wall. It's ok to visit cells more than once. Describe an algorithm for converting a given maze into a regular expression over the alphabet {U,D,L,R} which matches exactly those strings which correspond to sequences of moves which solve the maze. Your algorithm may call any algorithm presented in lectures; if you do this, you do not have to list the steps in the algorithm from lectures that you're calling. You are in a maze represented by a rectangular grid. One cell is the start cell, another is the cell you want to get to. Some pairs of adjacent cells have a wall between them, preventing you from moving directly from one to the other. There is at least one path from the start to the end. Suppose that the characters U, D, L, R. represent moving up, down, left and right by one grid cell. A string of these characters represents a sequence of movements through the maze, but is only valid if it does not make you bump into a wall. It's ok to visit cells more than once. Describe an algorithm for converting a given maze into a regular expression over the alphabet {U,D,L,R} which matches exactly those strings which correspond to sequences of moves which solve the maze. Your algorithm may call any algorithm presented in lectures; if you do this, you do not have to list the steps in the algorithm from lectures that you're calling.

Answer rating: 100% (QA)

We will use a backtracking algorithm We start at the start cell If the start cell is the end cel... View the full answer