National Olympiad in Informatics, China, 2001
At the military headquarters, the generals are planning the deployment
of their artillery squads using a map of an grid. One
map consists of rows of columns each. A cell on the grid can
represent land characterized by hills (denoted by an H
) or plains
(denoted by a P
), as depicted by the diagram below. On each cell
consisting of plains, at most one artillery squad may be positioned
(artillery teams may not be placed on hills). The attack range of a
single artillery squad is depicted by the black regions in the following
diagram.
If a gray cell represents one artillery squad on the map, then the black cells represent the cells that it can attack - horizontally two cells each from its left to its right, and vertically two cells each from above and below it. It cannot attack any white cells on the map. It can be deduced from the diagram that the shape of the land does not impact the squad's range of attack.
Now, the generals are planning how to position the artillery so that accidental injuries are prevented (they must ensure that no two artillery teams can attack each other, and that no artillery squad may be in another artillery squad's attack range). Under this condition, they would like to know the maximum number of their artillery squads that can be positioned onto the field.
Input Specification
The first line of input contains two space-separated positive integers
and . The next lines each contain
characters (either P
or H
), representing the map of the
battlefield.
Output Specification
The output should contain a single integer , the maximum number of artillery squads that may be positioned.
Sample Input
5 4
PHPP
PPHH
PPPP
PHPP
PHHP
Sample Output
6
Problem translated to English by .
Comments