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)