5. At each time step, an insect can move Up, Right, Down, or Left (but not diagonally) into an adjacent square if that square is currently free. Squares may be blocked by walls (as denoted by the black squares), but the map is known. You now control a single flea as shown in the maze above, which must reach a designated target location X. a) (5 pts). Show the order in which the squares are visited using a breadth-first search assuming the flea always tries to go up before right before down before left. b) (5 pts.) Show the order in which the squares are visited using a depth-first search assuming the flea always tries to go up before right before down before left. c) (5 pts.) Show the order in which the squares are visited using a A* search assuming the flea always tries to go up before right before down before left. d) (10 pts.) Perform the A* search again with the additional criteria. In addition to moving along the maze as usual, your flea can jump on top of the walls. When on a wall, the flea can walk along the top of the wall as it would when in the maze. It can also jump off of the wall, back into the maze. Jumping onto the wall has a cost of 2, while all other actions (including jumping back into the maze) have a cost of 1. Note that the flea can only jump onto walls that are in adjacent squares. 5. At each time step, an insect can move Up, Right, Down, or Left (but not diagonally) into an adjacent square if that square is currently free. Squares may be blocked by walls (as denoted by the black squares), but the map is known. You now control a single flea as shown in the maze above, which must reach a designated target location X. a) (5 pts). Show the order in which the squares are visited using a breadth-first search assuming the flea always tries to go up before right before down before left. b) (5 pts.) Show the order in which the squares are visited using a depth-first search assuming the flea always tries to go up before right before down before left. c) (5 pts.) Show the order in which the squares are visited using a A* search assuming the flea always tries to go up before right before down before left. d) (10 pts.) Perform the A* search again with the additional criteria. In addition to moving along the maze as usual, your flea can jump on top of the walls. When on a wall, the flea can walk along the top of the wall as it would when in the maze. It can also jump off of the wall, back into the maze. Jumping onto the wall has a cost of 2, while all other actions (including jumping back into the maze) have a cost of 1. Note that the flea can only jump onto walls that are in adjacent squares