{"problem":{"name":"[SHUPC 2024]  占地斗士！","description":{"content":"游戏的具体规则为：游戏在一个 $n\\times m$ 的方格矩阵中进行，`.` 代表这个格子可以被放置，`#` 代表这个格子不能被放置。你手中有 $4$ 种形状各异的卡牌，每种卡牌均**只有一张**。你需要将卡牌放置在棋盘中，卡牌可以放置在任意位置，但是卡牌占领的格子不能重叠，也不能放在不能放置的格子上。目标是要使得卡牌占领的格子数量尽可能多。 小 A 现在想知道，在最优的摆放策略下，最多可以占领","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P2"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10313"},"statements":[{"statement_type":"Markdown","content":"游戏的具体规则为：游戏在一个 $n\\times m$ 的方格矩阵中进行，`.` 代表这个格子可以被放置，`#` 代表这个格子不能被放置。你手中有 $4$ 种形状各异的卡牌，每种卡牌均**只有一张**。你需要将卡牌放置在棋盘中，卡牌可以放置在任意位置，但是卡牌占领的格子不能重叠，也不能放在不能放置的格子上。目标是要使得卡牌占领的格子数量尽可能多。\n小 A 现在想知道，在最优的摆放策略下，最多可以占领多少个格子？\n![](https://cdn.luogu.com.cn/upload/image_hosting/l9d77whu.png)\n\n## Input\n\n第一行输入两个正整数 $n,m\\ (1 \\le n,m\\le10) $\n\n接下来 $n$ 行，每行 $m$ 个字符串，保证字符仅包含 `.` 和 `#` ，代表棋盘的放置类型。\n\n## Output\n\n输出一个整数，代表答案。\n\n[samples]\n\n## Background\n\n一个名为“占地斗士”的卡牌小游戏深深的吸引了小 A\n。目前小 A 正在进行卡牌摆放练习，但是她并不熟练，于是想要请教擅长编程的你来解决这个问题。\n\n## Note\n\n样例解释：\n\n样例一最优摆放方法如下，使用第一种和第二种卡牌，最多可以占领 $9$ 个格子。\n\n![img1](https://cdn.luogu.com.cn/upload/image_hosting/zt41mdit.png)\n\n样例二最优摆放方法如下，使用第二种卡牌，最多可以占领 $4$ 个格子，红色代表这个格子不能放置卡牌。\n\n![img2](https://cdn.luogu.com.cn/upload/image_hosting/352061x2.png)","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10313","tags":["2024","高校校赛"],"sample_group":[["3 3\n...\n...\n...","9"],["3 3\n..#\n.#.\n#..","4"]],"created_at":"2026-03-03 11:09:25"}}