PROBLEM STATEMENT
Battleship is a game played on a 10x10 grid. The rows of the grid are referred
to by letters A-J (A is the topmost row, J is the bottommost row), while the
columns are referred to by numbers 1-10 (1 is the leftmost column, 10 is the
rightmost column). Five ships are placed on the grid: one ship of length 5,
one ship of length 4, two ships of length 3, and one ship of length 2. The
number of squares occupied by a ship is equal to its length. Moreover, each
ship may only occupy a continuous set of squares within one row or column (the
ships are straight and continuous and cannot be placed diagonally). Also, no
square can be occupied by more than one ship.
You want to find out if some squares on a battleship board are more likely to
contain a ship than others. Code a method which takes a String[] encoded
battleship boards and a square, and counts the amount of times that a ship was
present on that square.
DEFINITION
Class Name: BattleShip
Method Name: count
Parameters: String[], String
Return: int
Method signature (make sure your method is public):
int count(String[] boards, String square)
TopCoder will ensure the validity of the inputs. Inputs are valid if all of
the following criteria are met:
- square is a String of format "<row><col>" (quotes and brackets for clarity
only, they are not in the string)
- boards is a String[] with between 0 and 50 elements, inclusive
- Each element in boards has the format "<row><col><dir> <row><col><dir>
<row><col><dir> <row><col><dir> <row><col><dir>" (quotes and brackets for
clarity only, they are not in the string)
- <row> are row specifiers. characters 'A' through 'J' inclusive
- <col> are column specifiers. integer 1 through 10 inclusive
- <dir> are direction specifiers characters 'R','L','U','D'
- Each element in boards contains five <row><col><dir> tuples, each tuple
describing the position of a ship.
- The tuples are separated by a single space.
NOTES
- In each element of boards...
* The first tuple corresponds to the ship of length 5.
* The second tuple corresponds to the ship of length 4.
* The third and fourth tuples correspond to ships of length 3.
* The fifth tuple corresponds to the ship of length 2.
- TopCoder will ensure that each element in boards is valid, but you will have
to check if the element generates a valid board. Specifically, if a ship goes
off the board, or a square contains more than one ship, disregard the board.
For example "J10D B1R D1D I10U F6L" describes an invalid board. J10D describes
a ship of length 5 which starts at J10 and continues below that square, but
there are no squares below J10. "A1R A1R A1R A1R A1R" describes an invalid
board becuase the square A1 is occupied more than once. (See example 2)
EXAMPLES:
1.
count({"A1R B1R D1D J10U F6L"},"A1") gives the following board where X
represents a sqaure filled by a piece of a ship and O represents an empty square:
1 2 3 4 5 6 7 8 9 10
A X X X X X O O O O O
B X X X X O O O O O O
C O O O O O O O O O O
D X 0 0 0 0 0 0 0 0 0
E X 0 0 0 0 0 0 0 0 0
F X 0 0 0 X X 0 0 0 0
G 0 0 0 0 0 0 0 0 0 0
H 0 0 0 0 0 0 0 0 0 X
I 0 0 0 0 0 0 0 0 0 X
J 0 0 0 0 0 0 0 0 0 X
A1R refers to the ship of length 5. The ship starts at A1 and its remaining
portion is to the right of A1, namely A2, A3, A4, A5.
B1R refers to the ship of length 4. The ship starts at B1 and its remaining
portion is to the right of B1, namely B2, B3, B4.
D1D refers to a ship of length 3. The ship starts at D1 and its remaining
portion is below D1, namely E1, F1.
J10U refers to a ship of length 3. The ship starts at J10 and its remaining
portion is above J10, namely J9, J8.
F6L refers to the ship of length 2. The ship starts at F6 and its remaining
portion is to the left of F6, namely F5.
The return should be 1 because position A1 is occupied 1 time in the boards
String[].
2.
count({"A1R B1R D1D J10U F6L","A1R B1R D1D J10D F6L"},"A1") returns 1
The first board is just like the one shown above. A ship is present on square A1
The second board should be disregarded even though there is a ship present on
square A1 because J10D says to put a ship of length 3 starting at J10 and
orienting it down, but that would mean that the ship goes off the board.
3. count({"A1R B1R D1D J10U F6L","A1R B1R D1D J10U F6L"},"J1") returns 0
4. count({"A1R B1R D1D J10U F6L","A1R B1R D1D J10U F6L"},"B2") returns 2
5. count({},"J1") returns 0