Connection Status:
Competition Arena > TwoLineMinesweeper

TwoLineMinesweeper

2022 TCO Parallel 1B · 2022-04-14 · by misof

2022 TCO Parallel 1B · 2022-04-14 · by misof · Greedy, Simple Search, Iteration
Class Name: TwoLineMinesweeper
Return Type: String[]
Method Name: solve
Arg Types: (vector<int>)
Problem Statement

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.

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, 0}
Returns: {"------" }

If the first row is all zeros, there are no mines in the second row.

1)
{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.

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

3)
{2, 2, 2, 2, 2}
Returns: {"**-**" }

+---+---+---+---+---+ | 2 | 2 | 2 | 2 | 2 | +---+---+---+---+---+ | * | * | | * | * | +---+---+---+---+---+

4)
{0}
Returns: {"-" }

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

Coding Area

Language: C++17 · define a public class TwoLineMinesweeper with a public method vector<string> solve(vector<int> firstLine) · 122 test cases · 2 s / 256 MB per case

Submitting as anonymous