In a popular mobile app, two friends can play a game of battleship against one another. In this version of battleship, each player has a grid of squares in which they can place their ships vertically or horizontally. Each ship takes up a contiguous segment of grid squares equal to its length. For example on the left board below, the player has placed two ships of length
The rules of the app state that you are not allowed to place ships adjacent to one another. This means that two squares occupied by different ships must not share a side or a corner.
The players can't see their opponent's arrangement of ships. They take turns firing torpedoes blindly into their opponent's grid. Each torpedo hits one grid square. If there is a ship covering that square, it's a hit
. If not, it's a miss
. The game is over when one player has hit every grid square covered by an opponent's ship.
The board on the right above shows the other player's view of the board on the left after h
and misses m
.
In this version of the game, your opponent does not tell you when you have finished hitting a ship. In the example above, one of the length
The input will contain h
) and misses (m
) to the opponent's ships. All other grid squares will be filled with a .
character (ASCII
Note that the sample input below contains only
Sample Input
5 3
.....
.hm..
.....
.....
.....
Sample Output
14
Educational Computing Organization of Ontario - statements, test data and other materials can be found at ecoocs.org
Comments