[SHUPC 2024] 占地斗士!

Luogu
IDLGP10313
Time2000ms
Memory512MB
DifficultyP2
2024高校校赛
游戏的具体规则为:游戏在一个 $n\times m$ 的方格矩阵中进行,`.` 代表这个格子可以被放置,`#` 代表这个格子不能被放置。你手中有 $4$ 种形状各异的卡牌,每种卡牌均**只有一张**。你需要将卡牌放置在棋盘中,卡牌可以放置在任意位置,但是卡牌占领的格子不能重叠,也不能放在不能放置的格子上。目标是要使得卡牌占领的格子数量尽可能多。 小 A 现在想知道,在最优的摆放策略下,最多可以占领多少个格子? ![](https://cdn.luogu.com.cn/upload/image_hosting/l9d77whu.png) ## Input 第一行输入两个正整数 $n,m\ (1 \le n,m\le10) $ 接下来 $n$ 行,每行 $m$ 个字符串,保证字符仅包含 `.` 和 `#` ,代表棋盘的放置类型。 ## Output 输出一个整数,代表答案。 [samples] ## Background 一个名为“占地斗士”的卡牌小游戏深深的吸引了小 A 。目前小 A 正在进行卡牌摆放练习,但是她并不熟练,于是想要请教擅长编程的你来解决这个问题。 ## Note 样例解释: 样例一最优摆放方法如下,使用第一种和第二种卡牌,最多可以占领 $9$ 个格子。 ![img1](https://cdn.luogu.com.cn/upload/image_hosting/zt41mdit.png) 样例二最优摆放方法如下,使用第二种卡牌,最多可以占领 $4$ 个格子,红色代表这个格子不能放置卡牌。 ![img2](https://cdn.luogu.com.cn/upload/image_hosting/352061x2.png)
Samples
Input #1
3 3
...
...
...
Output #1
9
Input #2
3 3
..#
.#.
#..
Output #2
4
API Response (JSON)
{
  "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 现在想知道,在最优的摆放策略下,最多可以占领...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments