Statistics

Problem Statement for "MinePut"

Problem Statement

You are working on a program that randomly generates game boards for the well-known game SweepMines. In SweepMines, your goal is to reveal all cells in a 2-dimensional grid that contain mines. Each cell without a mine contains a digit representing the upper bound on the number of mines that may surround that cell, both orthogonally and diagonally. For example, if an empty cell has 3 neighboring cells with mines, it can contain any number between 3 and 9 (but not 0, 1 or 2). If a cell has no neighboring mines at all, it can contain any digit.

For instance, the board shown to the left is a valid board, while the one on the right is not because there is a mine adjacent to a cell that contains a 0 (here, '*' represents a mine).

11000          02210
*2921          1****
23**1          03332
*2251          *1000

You have already written a subroutine that has filled in the first few randomly chosen cells of the game board, which is given as a String[]. Each cell that your subroutine has generated represents either a blank space or a number representing the maximal number of mines that may surround that cell from the (up to) eight spaces around it. If a cell contains a blank space, then any number of mines may surround that cell. You may only place a mine in a blank cell.

Since you want the game to be as challenging as possible, you wish to find the maximal number of mines that the board may be filled with such that the resulting board configuration is valid. Note that a mine configuration is valid if and only if the number of mines surrounding each original non-blank cell is at most the number inside that cell.

Definition

Class:
MinePut
Method:
getMines
Parameters:
String[]
Returns:
int
Method signature:
int getMines(String[] partialBoard)
(be sure your method is public)

Notes

  • You may not place a mine in a filled cell; only a blank one.

Constraints

  • partialBoard will contain between 1 and 22 elements, inclusive.
  • Each element of partialBoard will contain between 1 and 22 characters, inclusive.
  • Each element of partialBoard will contain the same number of characters.
  • partialBoard will contain at most 22 characters.
  • Each element of partialBoard will contain only digits ('0'-'9') and '.' characters.

Examples

  1. { "0050", "0100", "0010", "3000"}

    Returns: 0

    It's impossible to place any mines.

  2. { ".100", "1100", "0000", "0000"}

    Returns: 1

    The only possible location for a mine is the upper left corner.

  3. { ".....", ".....", ".....", "....."}

    Returns: 20

    The entire board can be filled with mines.

  4. { "3.4..1", "2.21..", "999999"}

    Returns: 3

  5. { "......................"}

    Returns: 22

  6. { "....", ".99.", ".99.", "...."}

    Returns: 12

  7. { "....", ".11.", ".11.", "...."}

    Returns: 4

  8. { "2..2", "....", "....", "2..2"}

    Returns: 8

  9. { "1110", "1.12", ".2.1", "1211"}

    Returns: 2

  10. { "11.1", "1.22", "11.1", "0211"}

    Returns: 2

  11. { "99999", "99999", "99999"}

    Returns: 0

  12. { ".3..3", "..321", "112..", "..321"}

    Returns: 4

  13. { "3223", "2..2", "2..2", "1..0"}

    Returns: 3

  14. { "3223", "2..2", "2.02", "3223"}

    Returns: 0

  15. { ".......", ".......", "......." }

    Returns: 21

  16. { "...", "...", "...", "...", "...", "...", "..." }

    Returns: 21

  17. { "...........", "..........." }

    Returns: 22

  18. { "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", ".." }

    Returns: 22

  19. { "..", "..", "..", "..", "..", "..", "..", "5.", "..", "..", ".." }

    Returns: 21

  20. { "...........", "....8......" }

    Returns: 21

  21. { "...", "...", "9..", "...", "...", "...", "..." }

    Returns: 20

  22. { "...", "...", "...", "...", ".7.", "...", "..." }

    Returns: 19

  23. { ".653", ".5.4", "5.9.", "..5."}

    Returns: 8

  24. { "..11.1", "11.1.1", "..111."}

    Returns: 2

  25. { "01.2", "00..", "000.", "...."}

    Returns: 0

  26. { "."}

    Returns: 1

  27. { "9"}

    Returns: 0

  28. { "..9.9", "11111"}

    Returns: 2

  29. { "0"}

    Returns: 0

  30. { ".000.", "11111", ".....", "00.00"}

    Returns: 0

  31. {"3333", "....", "3333", "....", "3333" }

    Returns: 5

  32. {".1.", "121", ".10" }

    Returns: 2

  33. {"3333", "....", "3333", "....", "3333" }

    Returns: 5

  34. {".1.", "121", ".10" }

    Returns: 2

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.
This problem was used for: