Problem F
Battleship

In this exercise, you will program a computer game: Battleship! For the sake of simplicity, we will limit ourselves to a single-player mode with one board. At the start of the game, $5$ ships are placed on a grid with $10\times 10$ tiles.

The grid’s columns are numbered from $1$ to $10$ whereas the rows are labelled using the letters A to J (see image below). Individual coordinates are referenced by letter and number, e.g. D9 or J10.

Figure 1: Battleship grid

The ships are placed either horizontally or vertically on the grid. The ships sizes are as follows:

• The carrier is the biggest and occupies $5$ tiles.

• The battleship occupies $4$ tiles.

• The destroyer and submarine, both occupy $3$ tiles.

• Finally, the patrol boat that occupies $2$ tiles.

Input

The input starts with the program prompting the user for the location of each of the five ships with
“Location and orientation of your {ship type}: ”.
The second part of the input then consists of $n$ lines, where each line $n_i$ contains one attack.

In the tests, $n$ will be restricted to $17\le n\le 100$. It is also guaranteed that the placements of all ships will be valid, that is to say no ship overlaps another.

In the samples below, the first five lines contain the placement of the ships. The remaining $n$ lines each contain one attack made by the player.

Output

The output should start with $n$ lines, one for each attack the player made, where the program outputs one of the following:

• “Miss.” if the attack missed.

• “Hit, {ship type}.” if the attack hit a ship.

• “You have sunk my {ship type}.” if all of the ship’s tiles have now been attacked.

Then finally when all the ships have been sunk, the program should print “The entire fleet has been sunk.” and exit.

C3 vertical
A5 horizontal
A2 vertical
F6 horizontal
D7 vertical
D5
D3
C3
B3
E3
F3
G3
D1
C2
B2
A2
A5
A6
A7
A8
D7
E8
E7
F6
F7
F8

Location and orientation of your carrier:
Location and orientation of your battleship:
Location and orientation of your destroyer:
Location and orientation of your submarine:
Location and orientation of your patrol boat:
Miss.
Hit, carrier.
Hit, carrier.
Miss.
Hit, carrier.
Hit, carrier.
You have sunk my carrier.
Miss.
Hit, destroyer.
Hit, destroyer.
You have sunk my destroyer.
Hit, battleship.
Hit, battleship.
Hit, battleship.
You have sunk my battleship.
Hit, patrol boat.
Miss.
You have sunk my patrol boat.
Hit, submarine.
Hit, submarine.
You have sunk my submarine.
The entire fleet has been sunk.