National Olympiad in Informatics, China, 2001

Day 1, Problem 2 - Artillery Positioning

At the military headquarters, the generals are planning the deployment of their artillery squads using a map of an N×M grid. One N×M map consists of N rows of M 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 not attack any other 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 Format

The first line of input contains two space-separated positive integers N and M (N ≤ 100; M ≤ 10). The next N lines each contain M characters (either 'P' or 'H'), representing the map of the battlefield.

Output Format

The output should contain a single integer K, the maximum number of artillery squads that may be positioned.

Sample Input

5 4
PHPP
PPHH
PPPP
PHPP
PHHP

Sample Output

6

All Submissions
Best Solutions


Point Value: 20 (partial)
Time Limit: 1.00s
Memory Limit: 64M
Added: May 08, 2014

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

Constant optimization is annoying plz help.