Connection Status:
Competition Arena > MineMapper

MineMapper

SRM 118 · 2002-10-29 · by dgoodman

SRM 118 · 2002-10-29 · by dgoodman
Class Name: MineMapper
Return Type: int
Method Name: numClear
Arg Types: (vector<string>)
Problem Statement

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:
  1. 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.
  2. 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.
  3. 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.

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
0)
{"-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.

1)
{"-M-","M--","---"}
Returns: 1

.M- M-- --- The soldier knows where the 2 Mines are but cannot move anywhere to check on the rest of the field.

2)
{"--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.)

3)
{"-----","-----","--M-M","-M---","---M-"}
Returns: 18

".....", ".....", "..M.M", ".M-.-", "...M-"}; (A logician ignoring the manual could safely reach all 21.)

4)
{"--------------------------------------------------","--------------------------------------------------","MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM-","--------------------------------------------------","--------------------------------------------------","MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM-","--------------------------------------------------","--------------------------------------------------","MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM-","--------------------------------------------------","--------------------------------------------------","MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM-","--------------------------------------------------","--------------------------------------------------","MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM-","--------------------------------------------------","--------------------------------------------------","MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM-","--------------------------------------------------","--------------------------------------------------","MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM-","--------------------------------------------------","--------------------------------------------------","MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM-","--------------------------------------------------","--------------------------------------------------","MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM-","--------------------------------------------------","--------------------------------------------------","MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM-","--------------------------------------------------","--------------------------------------------------","MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM-","--------------------------------------------------","--------------------------------------------------","MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM-","--------------------------------------------------","--------------------------------------------------","MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM-","--------------------------------------------------","--------------------------------------------------","MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM-","--------------------------------------------------","--------------------------------------------------","MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM-","--------------------------------------------------","--------------------------------------------------","MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM-","--------------------------------------------------","--------------------------------------------------"}
Returns: 1716

Submissions are judged against all 37 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class MineMapper with a public method int numClear(vector<string> layout) · 37 test cases · 2 s / 256 MB per case

Submitting as anonymous