P13490 [GCJ 2008 Finals] The Year of Code Jam

2008 年将被称为变革与转折之年，是新时代的开始：我们当然说的是全新的 Google Code Jam 赛制。今年举办了如此多精彩的编程竞赛，以至于人们开始称其为“Code Jam 之年”。 热情的参赛者 Sphinny 正在查看她这一年的日历，发现有大量编程比赛已经安排好。她在日历上的每一天都做了如下三种标记之一： - 白色：这一天她不会参加比赛。要么没有比赛安排，要么她有更重要的事情要做（生活中肯定还有其他美好的事物！）。 - 蓝色：这一天她一定会参加比赛。 - 问号：这一天有比赛安排，但她还没有决定是否参加。 注意：为简化问题，我们假设没有资格赛的概念：你不需要参加某场比赛才能有资格参加另一场。 在 Sphinny 所处的世界中，她的日历有一些我们必须说明的特点：它有 $N$ 个月，每个月恰好有 $M$ 天。 下图展示了一个有 $5$ 个月、每月 $8$ 天、$15$ 个蓝色日和 $5$ 个问号的日历。  Sphinny 看着她漂亮的日历，决定每一天最多有 $4$ 个邻居：同一个月的前一天、同一个月的后一天、同一天的上一个月、同一天的下一个月。 Sphinny 希望通过这些比赛最大化她的幸福感，她估算幸福值的方法是对所有蓝色日的数值求和。对于每一个蓝色日，其数值计算如下： - 初始值为 $4$。 - 每有一个蓝色邻居，该日的数值减少 $1$。 你可能会觉得 Sphinny 很喜欢比赛，但连续两天参赛会让她有点疲惫。出于美学原因，在连续两个月的同一天参赛也不是很理想。 Sphinny 现在想要规划她的全年日程，决定每一个问号日到底是白色还是蓝色。她的目标很简单：让幸福值最大化。 下图展示了上述例子的一个解法。通过将两个问号改为蓝色日，将另外三个改为白色日，她可以获得 $42$ 的幸福值。 

输入文件的第一行包含用例数 $T$。接下来是 $T$ 个用例，每个用例如下格式。 第一行有 $2$ 个数：$N$ $M$，其中 $N$ 和 $M$ 分别表示月份数和每月天数。 接下来的 $N$ 行，每行包含一个长度为 $M$ 的字符串。第 $i$ 行第 $j$ 个字符属于 `.`、`#`、`?` 中的一个，分别表示第 $i$ 个月第 $j$ 天的状态。`#` 表示蓝色日，`.` 表示白色日，`?` 表示问号日。

对于每个输入用例，输出一行，格式如下： ```text Case #X: Y ``` 其中 $X$ 是用例编号（从 1 开始），$Y$ 是最大幸福值。

**样例说明** 请注意，第二个样例就是上面图片中的例子。 **数据范围** - $1 \leqslant T \leqslant 100$。 **小数据集（7 分，测试点 1 - 可见）** - 时间限制：~~30~~ 3 秒。 - $1 \leqslant M, N \leqslant 15$。 **大数据集（23 分，测试点 2 - 隐藏）** - 时间限制：~~120~~ 12 秒。 - $1 \leqslant M, N \leqslant 50$。 由 ChatGPT 4.1 翻译