A33019. 电路布线电路布局布线 (Circuit Layout and Routing) 是电子设计自动化 (EDA) 领域的一个重要概念，它涉及到在电路板或集成电路上安排和连接电子元件的过程。这个过程的目标是在满足电气性能、信号完整性、电磁兼容性等要求的同时，实现对空间、成本和生产工艺的优化。小小现在需要解决一个简化的电路布线问题，在一个 n × m 的方格中进行电路布线。其中： 井号 # 标记的格子已…
题目描述
电路布线
电路布局布线 (Circuit Layout and Routing) 是电子设计自动化 (EDA) 领域的一个重要概念，它涉及到在电路板或集成电路上安排和连接电子元件的过程。这个过程的目标是在满足电气性能、信号完整性、电磁兼容性等要求的同时，实现对空间、成本和生产工艺的优化。
小小现在需要解决一个简化的电路布线问题，在一个 n × m 的方格中进行电路布线。其中：
井号 # 标记的格子已经被占用，不能布线。
加号 + 标记的格子会连接到电路的其他部分，必须被布线。在给定的电路布线问题中，至少有一个格子必须被布线。
点号 . 标记的格子小小有权选择是否布线：布线即将该格标记为加号，不布线即保持为点号。
小小的任务是选择尽可能多的格子进行布线 (将 “.” 的格子标记为 “+”)，满足：
1. 布线电路连通。即从任意一个已布线的格子，都能通过上、下、左、右移动到相邻已布线格子的方式，到达任意另一个布线的格子。
2. 布线不存在短路 (回路)，即不存在某个布线的格子能通过 > 2 步的上、下、左、右移动到相邻布线格子的方式回到自身，且经过的格子各不相同。
例如，以下是一个电路布线问题，已有三个格子被标记为必须布线 (加号)：
#....#
....+#
.+####
.+...#
以下展示了一种合法和两种不合法的布线方案：
输入格式
输入第一行是两个空格分隔的整数 n 和 m，代表布线问题格子的行数和列数。
接下来 n 行，每行 m 个字符 (#, +, . 中的一个)，描述了具体的布线问题。
输入数据保证至少存在一种合法的布线方案。输入数据中至少有一个 +。
输出格式
输出 n 行，每行 m 个字符，代表最优的布线方案，其中被布线的格子尽可能多。如有多种可能的方案，输出任意一种即可。
样例输入 1
2 2
+.
..
样例输出 1
+.
++
样例输入 2
3 5
...+#
..###
....+
样例输出 2
++++#
.+###
+++++
样例输入 3
5 6
..++..
.#..#.
.#..#.
.#..#.
......
样例输出 3
++++++
+#.+#+
+#+.#+
+#++#+
++.+++
数据规模
对于 40% 的数据，满足 n × m ≤ 16。
对于 100% 的数据，满足 n, m ≤ 6。
评分标准
在你的布线方案合法 (连通且无回路) 的前提下：
如果你的方案是最优布线方案，即布线的格子最多，该测试点得满分。
否则，该测试点得一半分数。
参考答案
枚举法求解
如果我们为每一个可布线的格子 “.” 枚举是否布线，我们就得到了一个判定问题：判定某个具
体的布线是否满足连通和无回路的要求：
对于连通性，我们可以从任意 “+” 开始，使用深度优先/宽度优先搜索/迭代，找出所有可
达的加号。可达加号的数量必须和第一个连通块的数量一致。
对于无回路，我们可以检查连通块中的边数是否等于点数减一。
我们也可以遍历所有的边，并插入并查集数据结构来判定连通性和无回路。
连通性和回路的判定是非常基础的教科书算法问题。
算法优化
对于 6 × 6 的方格，至少有一个已布线的方格，我们需要检查 2 种不同的方案。我们可以通
过两种方式进行剪枝：
如果当前的解存在无法连通的方格或已经存在回路，则应剪枝。
如果当前的解无论如何都无法成为最优解，则应剪枝。我们需要为剩余部分的解估算一
个下界，例如剩下的方格总数。这种方法称为分支定界 (branch and bound)；
增加适当的搜索优化，可以通过大部分到全部测试用例。
一个有趣的思路是可以把电路分成上下两部分分别枚举，上半部分和下半部分枚举的数量都不
超过 2 = 262, 144。我们考虑上半部分的两种方案：
方案 1:
...++.
35
18
####++
方案 2:
+++++.
####++
毫无疑问，方案 2 是比方案 1 更 “好” 的——从下半部分看来，它们的 “接缝” 是完全一致的，但
方案 2 布了更多的线。因此，我们可以分别对上半部分和下半部分进行剪枝——对于同一种 “接
缝形状” 和连通性，我们只要保留布线数量最多的方案即可。在实际实现中，我们只需要排除
掉存在孤岛的不合法方案，即可通过所有测试用例。