BattleshipChecker

SRM 322 · 2006-10-09 · by soul-net

SRM 322 · 2006-10-09 · by soul-net · Search

Show categories

Class Name: BattleshipChecker

Return Type: String

Method Name: checkBoard

Arg Types: (vector<string>)

Problem Statement

Battleship is a game in which two players try to sink each other's ships. Each player has a 10x10 square grid on which he must place 10 ships. Each ship consists of between 1 and 4 cells arranged in a straight line. Ships must be placed parallel to the sides of the board, and no two ships can share a cell or touch each other. Touching is defined as occupying cells that share a vertex. Each player must place the following ships on his board: 4 ships of length 1, 3 of length 2, 2 of length 3, and 1 of length 4.

The effectiveness of a player's board is defined as the number of rows that contain no ships plus the number of columns that contain no ships. You will be given a String[] board, where each element represents one row of a player's board. If the board does not follow the above rules, return "REJECTED". If it does, return "ACCEPTED, X POINTS", where X is the effectiveness of the board, with no extra leading zeros.

Notes

The return value for an accepted board with a non-plural effectiveness must still end with "POINTS" (not "POINT").

Constraints

board will contain exactly 10 elements.
Each element of board will contain exactly 10 characters.
Each character of each element of board will be either '.' or 'X'.

Examples

{"......X...",
 ".XXX..X...",
 "......X...",
 "X.X...X...",
 "X.........",
 "...XX.X...",
 "......X...",
 ".XX...X...",
 "..........",
 ".X.X..X..."}
Returns: "ACCEPTED, 5 POINTS"

This one is correct, and has 4 free columns and 1 free row, for a total of 5 points.

{"X.X.X.X...",
 "......X...",
 ".XX...X...",
 "......X...",
 "......X..X",
 "...X..X...",
 "...X..X...",
 "......X...",
 "..XX..X...",
 "......X..."}
Returns: "REJECTED"

It is unacceptable to have a ship of size 1x10.

{".....XX...",
 ".XX.......",
 "..........",
 ".X....XXX.",
 ".X........",
 ".....X....",
 "..X..X....",
 ".....X....",
 "...X......",
 "X.....XXXX"}
Returns: "REJECTED"

One 1x1 ship is missing.

{".....XX..X",
 ".XX......X",
 "..........",
 ".X....XXX.",
 ".X........",
 ".....X..X.",
 "..X..X....",
 ".....X....",
 "...X......",
 "X.....XXXX"}
Returns: "REJECTED"

There is one extra 1x2 ship.

{".....XX..X",
 ".XX......X",
 "..........",
 "......XXX.",
 "..........",
 ".....X..X.",
 "..X..X....",
 ".....X....",
 "...X......",
 "X.....XXXX"}
Returns: "ACCEPTED, 3 POINTS"

{"X.......X.",
 "...XXXX...",
 ".X......X.",
 "....XX....",
 ".........X",
 ".........X",
 ".....XXX..",
 ".........X",
 "..X......X",
 "..X......X"}
Returns: "ACCEPTED, 0 POINTS"

This is a valid configuration even though it is not very effective.

{"X.......X.",
 "...XXXX...",
 ".X......X.",
 "....XX....",
 "...X.....X",
 "...X.....X",
 ".....XXX..",
 ".........X",
 ".........X",
 ".........X"}
Returns: "REJECTED"

Diagonal touching is not allowed.

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

Coding Area

Language: C++17 · define a public class BattleshipChecker with a public method string checkBoard(vector<string> board) · 74 test cases · 2 s / 256 MB per case