= Problem 1 (Mouse-in-a-maze). We will extend the warm-up example. Recall that in this problem, there is a mouse that is located at (0,0) and a cheese located at (m,n). The mouse can only move up (from (i,j) to (i +1, j)) or to the right (from (i,j) to (i, j +1)). Our goal is to count how many different paths does the mouse have to reach the cheese. In this problem, some places will contain obstacles, and in the input we are given an array b[0..m, 0..n] such that b[i, j] = 1 if and only if location (i,j) has an obstacle ((0,0) and (m,n) will never have obstacles). The mouse cannot touch any obstacles. (a) (6 points) Let a[i, j] denote the number of paths the mouse can take to reach (i,j). Write the transition function and specify the base cases for a[i, j]. (b) (8 points) Now assume the mouse can also jump from (i,j) to (i+2, j - 1) or (i 1, j+2) (as long as both coordinates are still nonnegative). Design an algorithm to count the number of paths the mouse can take to reach (m,n) (note that the mouse can reach (m, n) from (m-2, n+1) - there are no bounds on the side of m and n). (c) (6 points) Prove the correctness for the algorithm you designed in (b)