1. Calculate the size of a minimal state space for the problems below as an expression that references problem variables - M, N, P,1,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 Assume there are P Pacmen, numbered 1.P. Their turns cycle so Pacman 1 moves, then Pacman 2 moves, and so on. Pacman 1 moves again after Pacman P. 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. (ii) Suppose there is one Pacman. The walls are arranged such that they create a grid of H hallways total, which connect at I intersections. (In the example below, H = 9 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 H. (note: H = number of vertical hallways + number of horizontal hallways) (11)