A hungry mouse wants to eat all four fruits in a maze such as the one below, in as few moves as possible. At each turn the mouse can move any number of squares in one of the directions up, down, left or right, but it is not allowed to enter (or jump over) any walls (i.e., the black squares). Thus, the mouse moves just like a rook in chess. To eat a fruit, the mouse has to stop at that square. Assume that the maze has 4 fruits, and the size of b x h squares. 1. Give a suitable representation of the states in this searching problem. 2. How many possible actions can the mouse perform at each move? (I.e.. what is the branching factor?) e