Assume you have a 2D maze specified using text characters:

The symbols can be described as follows: . An empty space # A wall digit A number 1-9 representing an amount of treasure (in an otherwise empty space) m A stealthy, scary, smelly monster p A player starting location (on top of an empty space)

The player will explore as much of the maze as possible, collecting treasure... your treasure. You'd like to prevent this, and you have one more monster that you can place in the maze to deter the player. First, note the rules on player movement and mazes: - The player will explore every location or 'space' in the maze that can be safely reached from the player's starting location. The player cannot pass through walls, but can move into and out of spaces containing treasure. - The player will explore by repeatedly moving between spaces into adjacent spaces ('adjacent' defined as the four spaces located up, down, left, and right from the current location).

- The player will pick up all treasure when they explore a space containing treasure.

- The player can smell monsters in adjacent spaces, but the player cannot tell a direction. If the player enters a space with a monster adjacent to it, the player will collect any treasure in it and then very carefully, very quietly, and very quickly the player will go back the way they came. (For example: If the player moves south one space and then smells a monster in an adjacent space, the player will immediately go one space north.)

- The maze will always have a complete perimeter of walls.

- The maze will have a single starting location for the player.

- The maze may have multiple monsters, treasure spaces, and interior walls.

- There will never be a monster in or adjacent to the player's starting location.

- Mazes may have unreachable spaces, monsters, and/or treasure.

The problem Given a maze, determine any best empty space to place one more monster to minimize the amount of treasure the player will collect. The resulting maze must meet the criteria above. Your solution must implement some form of the WFS algorithm from the book and lecture -- your solution cannot use recursion. We'll look for the algorithm during grading - to avoid a significant deduction please make the WFS algorithm clear in your comments and code structure. (It is not allowed to use a library function that eliminates the need for you to write a traversal algorithm.) There will be a modest time limit on this problem.

Inputs

Your program will receive an integer number of rows and columns followed by one string of non- whitespace characters for each row of the maze. Each string will be on its own line (terminated

with a line break). The maze may be as small as 5x5 or as large as 200x200.

Output Your program should output three integers (and no other text): The coordinates of any best location to place a monster (a row followed by a column, 0-based, starting in the upper left), followed by an integer indicating how much treasure the player will collect (when the additional monster is ideally placed).

Hints Keep it simple. You've got the algorithm, WFS, for traversing a graph. Adapt it. You don't need to invent a new algorithm. You've got a graph implicitly described in the maze. Choose a simple way to identify a vertex. You don't need to convert the maze to a graph data structure. Also remember that you cannot use recursion. This problem begs for solution decomposition into helper functions. Your top-level solution code should be exceptionally easy to follow.