Problem R
Mini Battleship
Battleship is a game played by two players. Each player has their own grid, which is hidden from their opponent. Each player secretly places some ships on their grid. Each ship covers a horizontal or vertical straight line of one or more contiguous squares. Ships cannot overlap. All ships are considered distinct, even if they have the same size. The orientation of each ship is not important to the game, only the squares they occupy.
After placing their ships, the players then take turns taking shots at their opponent’s ships by calling out a coordinate of their opponent’s grid. The opponent must honestly say whether the shot was a hit or a miss. When all of a ship’s squares are hit, that ship sinks (“You sunk my battleship!!”). A player loses when all of their ships are sunk.
Bob is playing a game of Mini Battleship against Alice.
Regular Battleship is played on a
Bob wonders how many ship placements are possible on Alice’s
board given what he knows so far. The answer will be
Input
The first line of input contains two space-separated
integers
Each of the next
-
A character ‘X’ represents one of Bob’s shots that missed.
-
A character ‘O’ (Letter O, not zero) represents one of Bob’s shots that hit.
-
A dot (‘.’) represents a square where Bob has not yet taken a shot.
Each of the next
Output
Output a single integer, which is the number of ways the
Sample Input 1 | Sample Output 1 |
---|---|
4 3 .... .OX. .... O..X 3 2 1 |
132 |
Sample Input 2 | Sample Output 2 |
---|---|
4 4 .X.X .XX. ...X .... 1 2 3 4 |
6 |
Sample Input 3 | Sample Output 3 |
---|---|
2 2 .. .. 2 2 |
4 |