SP7777 ANARC09J - National Treasure

最近国家博物馆的大展厅多次遭到抢劫，大家对展品的安全都非常担忧。为了增强大厅的安全性，博物馆聘请了一家私人安保公司，以提供额外的保安。这些保安将负责守护古老的文物。博物馆希望通过雇佣最少数量的保安来确保大厅的安全。大厅用一个 $R \times C$ 的二维网格表示，其中一些单元格已经被博物馆的保安占据，而其余的单元格则存放着各种不同类型的文物（如雕像、雕塑等），这些文物可以被新雇佣的保安替换。对于每件文物，根据其价值、存放的保险柜类型和其他因素，大厅中的某些其他单元格被标记为这件文物的关键点。如果要继续将这件文物留在大厅内，那么它的所有关键点都必须有保安驻守。同时，一个保安如果站在多个文物的关键点上，可以同时监控这些文物。不过，保安不能直接站在有文物的单元格上，你可以将文物移开来让保安驻守那里，但不能移走文物后让位置空着（只能替换成保安）。经过调查，你发现每件文物的关键点总是下图中那 12 个相邻单元格的子集。  因此，文物的类型可以用一个非负整数表示：当且仅当上图中的第 $i$ 个关键点是该文物的关键点时，第 $i$ 位为 1。例如，类型为 595（二进制 1001010011）的文物，其关键点分布如下图所示。注意这些位是从右至左编号的（最右边是第 1 位）。如果某文物的关键点落在大厅网格之外，视为已安全。  现给出大厅的布局，请找出需要新雇的最少保安数量，以确保所有剩余文物的安全。

你的程序将接收一个或多个测试用例。每个测试用例包含 $R+1$ 行。第一行输入两个整数 $1 \le R, C \le 500$，代表大厅的行数和列数。接下来的 $R$ 行，每行包括 $C$ 个字符，描述厅内布局。每个字符可以是以下几种： - `.`：空单元格。 - `#`：已由保安驻守的单元格。 - `0` 到 `9` 或 `A` 到 `F`：十六进制数字，表示文物的类型（十进制不超过 4095）。 输入保证至少有一个空单元格或已有保安的单元格。

对于每个测试用例，输出一行： ``` k. G ``` 其中 $k$ 是测试用例编号（从 1 开始），$G$ 是需要增加的最少保安数量，以确保所有剩余文物的安全。 **本翻译由 AI 自动生成**