ZOJ Problem Set - 1302
Probably everyone who ever attended school knows the game where two opposing players place a set of ships on a sheet of paper and try to eliminate each other's ships by guessing their location.
In our version of the game, your opponent has distributed the following seven ship patterns over a rectangular grid of squares:
xx xx xx x x x xx xx xx xxx xxx xxx xxxx
Each ship pattern covers exactly four squares. The patterns may be rotated but not mirrored. All patterns are guaranteed to be placed completely within the boundaries of the rectangle and not to overlap each other, whereas touching another pattern or the border is allowed.
We assume that we are in the middle of the game and that several squares have already been uncovered. You will be given a rectangular grid of squares representing your current knowledge about the positions of your enemy's ships. Every square is marked by one of the following characters:
`x' if a ship covers the square
Each of the next h lines contains a string of w characters. Each of these characters is either `x', `o' or `.', depending on the state of the corresponding square.
A blank line separates each game from the next. The input ends with a game having w = 0 and h = 0. This game should not be processed.
Output a blank line after every game.
Source: Southwest Europe 1996