{"trustable":true,"sections":[{"title":"問題の説明","value":{"format":"MD","content":"**元の問題:NOI 2001**\n\n司令部の将軍たちは、$N\\times M$の格子地図上に砲兵部隊を展開することにしました。 $N\\times M$の地図は、$N$行$M$列で構成され、地図の各マスには山地(`H`で表される)または平原(`P`で表される)のいずれかがあります。以下は地図の例です。平原地形の各マスには最大で1つの砲兵部隊を配置できます(山地には砲兵部隊を配置できません)。砲兵部隊の攻撃範囲は以下の黒い領域で示されています:\n\n![cannon.jpeg](CDN_BASE_URL/4bf6168d2234dc699daa2ffe53d7c078?v\u003d1701483990)\n\n地図の灰色で示された平原に砲兵部隊を配置すると、黒いマスがその攻撃範囲を示します:横方向に2マス、縦方向に2マス。他の白いマスには攻撃できません。地形の影響を受けずに砲兵の攻撃範囲が決まります。 \n今、将軍たちは誤射を防ぎつつ(つまり、任意の2つの砲兵部隊が互いに攻撃しないように、つまり任意の1つの砲兵部隊が他の砲兵部隊の攻撃範囲内にないように)、地図全体で最大限の砲兵部隊を配置する計画を立てています。"}},{"title":"入力フォーマット","value":{"format":"MD","content":"最初の行には、スペースで区切られた2つの正の整数が含まれており、それぞれ$N$と$M$を表します。 \n次の$N$行には、それぞれ連続する$M$文字(`P`または`H`)が含まれており、間に空白はありません。地図の各行のデータを順番に表します。"}},{"title":"出力フォーマット","value":{"format":"MD","content":"1行だけで、整数$K$が含まれており、配置できる砲兵部隊の最大数を表します。"}},{"title":"例","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":"データ範囲とヒント","value":{"format":"MD","content":"$N \\le 100, M \\le 10$。"}}]}