1. Calculate the size of a minimal state space for the problems below as an expression that references problem variables - M, N, P, I, H. Explain your calculations. A maze has height M and width N. A Pacman can move NORTH, SOUTH, EAST, or WEST. There is initially a pellet in every position of the maze. The goal is to eat all of the pellets. Note that the questions below are independent. (0) (ii) Assume there are P Pacmen, numbered 1,...,P. Their turns cycle such that all the odd numbered pacmans move one by one and then the even numbered ones move one by one. 1.e., Pacman 1 moves, then Pacman 3 moves, and so on and then Pacman 2 moves, Pacman moves and so on. Pacman 1 moves again after all the pacmans have moved once. Any time two Pacmen enter adjacent positions, the one with the lower number dies and is removed from the maze. Suppose there is one Pacman. Whenever Pacman enters a position which he has visited previously, the maze is reset - each position gets refilled with food and the "visited status" of each position is reset as well. Suppose there is one Pacman. The walls are arranged such that they create a grid of C Corridors total, which connect at I intersections. (In the example below, C = 9 (4 horizontal corridors and 5 vertical corridors) and I = 20). In a single action, Pacman can move from one intersection into an adjacent intersection, eating all the dots along the way. Your answer should only depend on I and C. (ili) PO