MineMapper | Topcoder Archive

Problem Statement

We want to send a soldier into a mine field with a non-directional (cheap) metal detector. The field is an n by n grid, and the soldier will move horizontally or vertically through the field, marking squares on his map. His metal detector will tell him how many adjacent (not diagonally) squares contain mines. He will follow the rules in his manual:

If your detector indicates that all the adjacent squares, except for ones that you have already walked on, contain mines then you may mark them as containing mines.
You may walk on a new square only if your detector indicates that the number of adjacent mines is equal to the number of adjacent squares already marked as containing mines.
Walk around, backtracking as needed, until you are sure that you have visited all the squares that you possibly can while following these rules.

We know that we could train logicians to make more complex inferences and be able to do better than this safely, but we want to see how well we will be able to do using the untrained soldiers. Create a class MineMapper that contains a method numClear that takes the actual layout of mines in a square minefield as input and that returns the number of squares that the soldier can visit while following the manual rules.

The layout shows the mine field as a String[], starting with the top row. '-' denotes a square with no mine and "M' denotes a square that contains a mine. The soldier will always start in the leftmost square in the top row, which will never contain a mine.

Definition

Class:: MineMapper
Method:: numClear
Parameters:: String[]
Returns:: int
Method signature:: int numClear(String[] layout)
(be sure your method is public)

Constraints

layout contains between 2 and 50 elements inclusive
the length of each element of layout equals the number of elements in layout
each character in layout will be a hyphen ('-') or upper case 'M'
the first character in the first element of layout will be a hyphen

Examples

```
{"-M-","---","---"}
```
```
Returns: 1
```
In all examples '.' instead of '-' shows squares visited by soldier .M- --- --- The soldier cannot determine which place to move from the initial square.
```
{"--M-","-MM-","----","----"}
```
```
Returns: 13
```
..M. .MM. .... .... The soldier moves right, determines the 2 mine locations. Then he backtracks and goes down. His detector says there is one adjacent mine, but he has marked the mine on the second row, second column. So he can safely go down to the third row. He can continue exploring and eventually get safely to all the non-mine squares.(He can determine the position of the remaining mine by first visiting all the squares in the bottom two rows and then standing on the square below the unmarked mine -- his detector will show that there is one adjacent mine and the soldier knows about the other three squares.)
```
{"-----","-----","--M-M","-M---","---M-"}
```
```
Returns: 18
```
".....", ".....", "..M.M", ".M-.-", "...M-"}; (A logician ignoring the manual could safely reach all 21.)

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.