A mad scientist has been performing experiments on mice's memory capabilities. He puts a mouse into a very large maze, which is scattered with food and water. There is one entrance, one exit. The maze is so big that if the mouse can't find food or water often enough it will starve or dehydrate, and pass out. When it passes out the mouse is restored to health by the scientist, and put back to the entrance. Eventually the mouse finds its way out of the maze, and seems to remember where its been. This scientist has asked you to model this situation, and write and a program that could do the same task as the mouse.
You are given a 20x20 maze, scattered with food and water, with one entrance and one exit. You must find a path that the mouse could survive from the entrance to the exit.
The mouse is full with food and water every time it is placed at the entrance ( with its maximum 12 units of food and 3 units of water ). Each square the mouse moves uses up one unit of each. When the mouse gets to a food or water dispenser the mouse automatically fills up, then the dispenser is removed ( it can not overfill itself, and the dispenser is put back if the mouse is put back to the entrance ). The mouse may only move N,S, E, & W, not diagonally. The mouse starves or dehydrates when it reaches 0 food or water.
The maze is given in an input named maze.in. The output maze should be created to be maze.out. The input maze uses the following symbols:
You can assume that the input file only contains the necessary 20 lines. The output maze should look exactly like the input one, except that '.''s will mark the path from the entrance to the exit. Also, after the maze, the output file should contain a directional listing of how the mouse got out of the maze, and it's current food/water stores after each leg. The format of that is to be: