Problem Statement
This problem references the well-known puzzle game Minesweeper. Prior knowledge of the game is not necessary, the problem statement explains everything you need to know.
You are playing Minesweeper on a small rectangular grid: two rows by N columns.
All the cells in the first row have already been revealed. It turned out that none of them contained a mine.
In Minesweeper, once a cell is revealed, it contains a number. The number shown in a revealed cell is the total number of mines in adjacent cells. (Cells sharing a side or a corner with that cell count as adjacent cells.)
You are given the int[] firstLine with N elements: these revealed numbers, from left to right.
Your task is to reconstruct the second row: find out which cells contain mines and which ones are empty.
We will use the character '*' (asterisk) to denote a mine and the character '-' (dash) to denote an empty cell. Using these characters we can describe the content of the second row as an N-character String.
It is possible that more than one configuration of mines corresponds to the given first row. If there are more than 50 such configurations, return a String[] containing any 50 distinct valid configurations of mines. If there are 50 or fewer, return a String containing all of them.
The return value must be sorted in ascending order.
Definition
- Class:
- TwoLineMinesweeper
- Method:
- solve
- Parameters:
- int[]
- Returns:
- String[]
- Method signature:
- String[] solve(int[] firstLine)
- (be sure your method is public)
Notes
- The sort order required is the standard sort order according to the characters' ASCII values. In this order, '*' < '-'. The standard sorting routine in each supported programming language should produce the correct order.
Constraints
- firstLine will have between 1 and 50 elements, inclusive.
- Each element of firstLine will be between 0 and 3, inclusive.
- firstLine will correspond to at least one valid placement of mines into the second row.
Examples
{0, 0, 0, 0, 0, 0}Returns: {"------" }If the first row is all zeros, there are no mines in the second row.{0, 0, 1, 1, 1, 0}Returns: {"---*--" }The second row must contain a single mine: +---+---+---+---+---+---+ | 0 | 0 | 1 | 1 | 1 | 0 | +---+---+---+---+---+---+ | | | | * | | | +---+---+---+---+---+---+ Three first row cells are adjacent to this mine.{1, 1}Returns: {"*-", "-*" }There are two solutions here: +---+---+ +---+---+ | 1 | 1 | | 1 | 1 | +---+---+ +---+---+ | * | | | | * | +---+---+ +---+---+ Please note that the answers must be in sorted order. The string "*-" comes before the string "-*".{2, 2, 2, 2, 2}Returns: {"**-**" }+---+---+---+---+---+ | 2 | 2 | 2 | 2 | 2 | +---+---+---+---+---+ | * | * | | * | * | +---+---+---+---+---+