CF97A Domino
题目描述
小 Gennady 在生日时收到了一个多米诺骨牌套装。这个套装包含 $28$ 个不同的尺寸为 $2×1$ 的多米诺骨牌。每个多米诺的两半分别写有 $0$ 到 $6$ 之间的一个数字。
`0-0 0-1 0-2 0-3 0-4 0-5 0-6
1-1 1-2 1-3 1-4 1-5 1-6
2-2 2-3 2-4 2-5 2-6
3-3 3-4 3-5 3-6
4-4 4-5 4-6
5-5 5-6
6-6
` 如果可以用 $28$ 个多米诺完全覆盖一个区域，并且可以将其分为 $14$ 个互不重叠的 $2×2$ 正方形，且每个正方形都只包含相同的数字，这个图形被称作“魔法图形”。每当 Gennady 拼出一个魔法图形时，他就能赢得下一个比赛。Gennady 还注意到，如果他拼过同样的图形，再拼一次就不能获胜。  Gennady 选择了一个 $n×m$ 的带格子的场地，并在上面摆放了 $1×2$ 和 $2×1$ 的矩形骨牌。每张骨牌正好覆盖场地上的两个相邻格子。骨牌之间不能重叠，但可以相互接触。场地上一共有 $28$ 张骨牌，和套装中的骨牌数量相同。现在 Gennady 想将每块骨牌替换为一块多米诺，使得最终拼出的图形是魔法图形。不同的骨牌必须用不同的多米诺替换。请你计算，按照当前骨牌的摆放方式，Gennady 能赢几场比赛。你还需要给出一种具体的多米诺分配方案，使他能赢得下一场比赛。
1-1 1-2 1-3 1-4 1-5 1-6
2-2 2-3 2-4 2-5 2-6
3-3 3-4 3-5 3-6
4-4 4-5 4-6
5-5 5-6
6-6
` 如果可以用 $28$ 个多米诺完全覆盖一个区域，并且可以将其分为 $14$ 个互不重叠的 $2×2$ 正方形，且每个正方形都只包含相同的数字，这个图形被称作“魔法图形”。每当 Gennady 拼出一个魔法图形时，他就能赢得下一个比赛。Gennady 还注意到，如果他拼过同样的图形，再拼一次就不能获胜。  Gennady 选择了一个 $n×m$ 的带格子的场地，并在上面摆放了 $1×2$ 和 $2×1$ 的矩形骨牌。每张骨牌正好覆盖场地上的两个相邻格子。骨牌之间不能重叠，但可以相互接触。场地上一共有 $28$ 张骨牌，和套装中的骨牌数量相同。现在 Gennady 想将每块骨牌替换为一块多米诺，使得最终拼出的图形是魔法图形。不同的骨牌必须用不同的多米诺替换。请你计算，按照当前骨牌的摆放方式，Gennady 能赢几场比赛。你还需要给出一种具体的多米诺分配方案，使他能赢得下一场比赛。
输入格式
第一行包含两个正整数 $n$ 和 $m$（$1 \le n,m \le 30$）。接下来的 $n$ 行，每行包含 $m$ 个字符，表示场地上骨牌的位置。点号表示空格，从字母 'a' 到 'z' 以及 'A', 'B' 表示骨牌的位置。相同字母代表同一块骨牌，不同字母代表不同骨牌。场地上恰有 $28$ 块骨牌，并且保证输入描述合法。
保证至少存在一种可行解。
输出格式
第一行输出能满足魔法图形条件的分配方案总数。接下来的 $n$ 行，每行 $m$ 个字符，分别输出一种合理的数字分配方案，用数字 $0$ 到 $6$ 代替各个骨牌的编号，空格用点号表示。所有的多米诺必须互不相同。
说明/提示
由 ChatGPT 5 翻译