Figure below shows an example maze. In the maze, black cells are walls, which are obstacles that you

can

$$

t move through. You can move on the white cells and you cannot move beyond the boundaries of

the maze. In each maze, the starting location will be the square of

$[$

$0$

$,$

$0$

$]$

$.$

$$Additionally$,$ there is also one

white cell labeled with F

$.$

$$This label shows the exit square of the maze. So

$,$

$$you must extract the path

from S to F

$.$

$$You can move in

$4$

$$directions; up

$,$

$$down$,$ left, right. These

$4$

$$directions will be represented by

characters U

$,$

$$D

$,$

$$L

$,$

$$and R

$,$

$$respectively$.$

The solution for the maze shown above is

$"$

D D R R R R D D

$"$

$,$

$$which means move down

$2$

$$times$,$ then

move right

$4$

$$times and move down

$2$

$$times$.$ The maze a simple one way road and it has only one

solution: there is always one possible next square for each move.In Scheme, a maze will be represented in the form of a linked

$-$

list. Figure below shows how the maze in

the first page is represented in terms of a linked list in Scheme. Starting cell

$[$

$0$

$,$

$0$

$]$

$$has the letter S

$,$

$$the

finishing cell has the letter F and empty cells have the letter E

$.$

$$The walls have the letter

$-$

$($

minus

$)$

$.$

$$

The following function "buildMaze" on the left is given for you which takes a list of lists and creates

a maze using the lists. You can use this function to create different mazes in order to test your code.

On the right the code shows how the maze in the Figure above is created.

$($

define

$($

buildMaze rows

$)$

$$

$($

cond

$($

$($

null

$?$

$$rows

$)$

$$null

$)$

$$

$($

else

$($

cons

$($

buildMaze

$($

cdr rows

$)$

$)$

$$

$($

car rows

$)$

$)$

$)$

$)$

$)$

$$

$($

define sampleMaze

$($

buildMaze

$\text{'}$

$($

$($

$"$

S

$"$

$"$

$-$

$"$

$"$

$-$

$"$

$"$

$-$

$"$

$"$

$-$

$"$

$)$

$$

$($

$"$

E

$"$

$"$

$-$

$"$

$"$

$-$

$"$

$"$

$-$

$"$

$"$

$-$

$"$

$)$

$$

$($

$"$

E

$"$

$"$

E

$"$

$"$

E

$"$

$"$

E

$"$

$"$

E

$"$

$)$

$$

$($

$"$

$-$

$"$

$"$

$-$

$"$

$"$

$-$

$"$

$"$

$-$

$"$

$"$

E

$"$

$)$

$$

$($

$"$

$-$

$"$

$"$

$-$

$"$

$"$

$-$

$"$

$"$

$-$

$"$

$"$

F

$"$

$)$

$)$

$)$

$)$

$$

Task

$1$

: Define two functions "getHeight" and "getWidth" which takes a maze as an input and

returns the height and the width of the maze.

$($

getHeight sampleMaze

$)$

$-$

$>$

$$should return

$5$

$($

getWidth sampleMaze

$)$

$-$

$>$

$$should return

$5$

Task

$2$

: Define a function "getLetter" which takes a maze, a row number and a column number.

Then it returns the letter from the maze on the corresponding location

$[$

row

$,$

$$column

$]$

$$

$($

getLetter sampleMaze

$0$

$0$

$)$

$$ should return S

$($

getLetter sampleMaze

$1$

$0$

$)$

$-$

$>$

$$should return E

$($

getLetter sampleMaze

$1$

$1$

$)$

$-$

$>$

$$should return

$-$

$($

getLetter sampleMaze

$4$

$4$

$)$

$-$

$>$

$$should return F

Task

$3$

: Define a function "solveMaze" which takes a maze and returns the solution for the maze.

$($

solveMaze sampleMaze

$)$

$-$

$>$

$$should return

$($

D D R R R R D D

$)$