Connection Status:
Competition Arena > OneBattleship

OneBattleship

SRM 821 · 2022-01-07 · by misof

SRM 821 · 2022-01-07 · by misof · Greedy, Math
Class Name: OneBattleship
Return Type: String[]
Method Name: hit
Arg Types: (vector<string>)
Problem Statement

Problem Statement

We are playing a simple version of the Battleships game.

The game is played on a rectangular grid of cells. Somewhere in the grid there is a single hidden battleship. The battleship occupies three consecutive cells (either vertically or horizontally).

You are given the current map of the grid in the String[] grid. Each character represents one cell. 'W' is a cell known to contain water, '.' is an unknown cell that may still belong to the battleship.

The game is played by firing shots. Each shot hits one of the cells in the grid. In our game, your goal is to hit the battleship at least once. (It is not necessary to hit all three cells of the battleship, any one of them is enough.)

Let N be the number of '.' cells currently in the grid. Find any set of at most N/3 shots that is guaranteed to win the game. Return your solution in the same format as the input, using '*' for cells where you want to fire your shots.

Notes

  • For the given constraints a solution always exists.
  • Each cell you did not shoot must contain the same character in your return value as it did in grid.
  • You are allowed to shoot 'W' cells (even though this does not help you find the battleship).

Constraints

  • grid will contain between 1 and 50 rows, inclusive.
  • Each element of grid will contain the same number of characters.
  • Each element of grid will contain between 1 and 50 characters, inclusive.
  • Each character in grid will be 'W' or '.'.
  • In grid, there will be at least one group of three consecutive '.' characters (horizontally or vertically).
Examples
0)
{"WW.WW",
 "WW.WW",
 ".....",
 "WW.WW",
 "WW.WW"}
Returns: {"WW.WW", "WW.WW", "..*..", "WW.WW", "WW.WW" }

There are six possible positions for the battleship. Two of them are shown below using 'B' for the battleship cells. WW.WW WW.WW WW.WW WW.WW .BBB. ..B.. WW.WW WWBWW WW.WW WWBWW Regardless of where the battleship is hiding, we can hit it by shooting the middle cell of the grid. (Other valid solutions with at most 3 shots will also be accepted.)

1)
{".W......."}
Returns: {".W..*.*.." }

We have 8 unknown cells, so we can make at most 8/3 shots. Hence, two shots is still OK but three shots is already too many. The leftmost unknown cell cannot be a part of the battleship, so we can just ignore it. The two shots shown in the return value are guaranteed to hit the battleship. (This is not the only possible solution.)

2)
{"W.W.W.W.",
 ".W.W.W.W",
 "W.W.W.W.",
 ".W.W.W.W",
 "W.W.W.W.",
 "...W.W.W"}
Returns: {"W.W.W.W.", ".W.W.W.W", "W.W.W.W.", ".W.W.W.W", "W*W.W.W.", "***W.W.W" }

On this board we can tell where the battleship is hiding and we can hit it using a single shot. The statement allows us to make up to 8 shots, so in our example return value we make four shots.

3)
{"...",
 ".W.",
 "..."}
Returns: {"..*", ".W.", "*.." }

We should shoot two opposite corners of this grid.

4)
{"...",
 "...",
 "..."}
Returns: {"*..", "..*", ".*." }

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

Coding Area

Language: C++17 · define a public class OneBattleship with a public method vector<string> hit(vector<string> grid) · 108 test cases · 2 s / 256 MB per case

Submitting as anonymous