{"trustable":true,"sections":[{"title":"题目描述","value":{"format":"MD","content":"**Original question from: NOI 2001**\n\nThe generals of the headquarters plan to deploy their artillery forces on a $N\\times M$ grid map. A $N\\times M$ map consists of $N$ rows and $M$ columns. Each grid of the map may be a mountain (denoted by `H`) or a plain (denoted by `P`), as shown in the following figure. At most one artillery force can be deployed on each grid of the plain terrain (artillery forces cannot be deployed on the mountain terrain); the attack range of an artillery force on a plain terrain is shown in the black area of the figure:\n\n![cannon.jpeg](CDN_BASE_URL/4bf6168d2234dc699daa2ffe53d7c078?v\u003d1701483990)\n\nIf an artillery force is deployed on the plain terrain marked in gray on the map, the black grids in the figure represent the area it can attack: two grids to the left and right horizontally, and two grids up and down vertically. It can be seen from the figure that the attack range of the artillery is not affected by the terrain. \nNow, the generals plan to deploy artillery forces, ensuring that no two artillery forces can attack each other (i.e., no artillery force is within the attack range of any other artillery force), and want to maximize the number of artillery forces that can be deployed in the entire map area, while avoiding friendly fire."}},{"title":"Input Format","value":{"format":"MD","content":"The first line contains two positive integers separated by a space, representing $N$ and $M$ respectively; \nThe next $N$ lines each contain a sequence of $M$ characters (`P` or `H`) with no spaces in between, representing the data of each row of the map in order."}},{"title":"Output Format","value":{"format":"MD","content":"Only one line containing an integer $K$, representing the maximum number of artillery forces that can be deployed."}},{"title":"Example","value":{"format":"MD","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e5 4\nPHPP\nPPHH\nPPPP\nPHPP\nPHHP\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e6\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"Data Range and Hints","value":{"format":"MD","content":"$N \\le 100, M \\le 10$."}}]}