$5(20$ pts$.)$ Greedy maze

You are in a $2-$dimensional maze, looking for the exit. You know your current position in the

maze and the position of the exit in terms of Cartesian coordinates. At each cell of the maze,

you can observe only the neighboring cells. If there is no wall preventing your move, you may

move up$,$ down, left or right by a cell.

See the example above. You are at cell marked $\text{'}C\text{'}$ trying to get the exit marked $\text{'}E\text{'}.$ Among

the $4$ options, the cell to your right is blocked by a wall. Cells marked $\text{'}?\text{'}$ are un$-$observable

from your current position. This means any cell with $\text{'}?\text{'}$ might reveal a wall later on$.$

Consider the following greedy heuristic for exiting the maze. From your current position, you

always move to an available cell that minimizes the distance from the exit. For the example

above, this implies either moving up or down. Moving left would increase the distance to $\text{'}E\text{'}.$

Assume that when there are multiple permissible moves, one will be picked randomly.

Answer the following for this algorithm.

$($a$)(7$ pts$.)$ Argue that this algorithm indeed is greedy.

$($b$)(7$ pts$.)$ Assuming there is one, does this strategy always yield a solution? Prove mathe$-$

matically or disprove by with a counter$-$example.

$($c$)(6$ pts$.)$ Is this strategy optimal? Prove mathematically or disprove by with a counter$-$

example.

In parts $($b$)$ and $($c$),$ if you pick to prove with a counter$-$example, give a full configuration

including to starting position $\text{'}C\text{'},$ the exit $\text{'}E\text{'}$ and all the walls.