Problem 3. (20 pts) Give an algorithm that solves mazes. maze is a rectangular maze with r rows and c columns, given in the form of a function Iswall(i,j, D) that tells you, in O(1)-time, whether you can or cannot move from square (i,j) in direction D (where D (Up, Down, Left,Right]). You are also given a start position s = (i, j) and a finish position f = (i, j'). Your goal is to find the shortest path taking you from s to f (if such a path exists). Your algorithm must run in O(r c) time. Explain why your algorithm is correct and why its runtime is O(r c). -| | L Figure 1: A rectangular maze