Question $1($Avery and the Wolf, $45$ points$).$ Avery is trapped in a maze with a wolf. The maze consists of an n $$ n grid of squares with some of the boundaries between adjacent squares occupied by walls. Avery can travel between adjacent squares if the boundary is not occupied by a wall, but for every such move the wolf will try to move twice. First, it will attempt to move one square left or right in the direction of Avery$$s current column, failing to move if the wolf is already in the same column as Avery or if the attempted move is blocked by a wall. Next, the wolf will attempt to move one square up or down in the direction of Avery$$s current row, failing to move if the wolf is already in the same row as Avery or if the attempted move is blocked by a wall. One of the squares in the maze is marked as an exit and Avery is trying to reach this exit before the wolf catches her. $($a$)$ Give an algorithm that given n$,$ a description of the locations of the walls, and a description of the initial locations of Avery, the wolf and the exit square determines whether it is possible for Avery to reach the exit square without the wolf first ending up on the same square as her. For full credit your algorithm should run in time polynomial in n$.[30$ points$]($b$)$ Give a brief description of how you would modify the algorithm to account for the following changes to the problem statement $($you do not need to provide new runtime or correctness proofs$)$: $($i$)$ If some specified walls have holes that Avery but not the wolf can travel through. $[5$ points$]($ii$)$ If the wolf travels as many squares left$/$right or up$/$down as possible until it either hits Avery$$s column$/$row or hits a wall $($instead of just one square left$/$right and one square up$/$down$).[5$ points$]($iii$)$ If instead of trying to reach a given exit square, Avery wants to lead the wolf to a specified trap square. $[5$ points$]$