{"problem":{"name":"[信息与未来 2023] 电路布线","description":{"content":"电路布局布线（Circuit Layout and Routing）是电子设计自动化（EDA）领域的一个重要概念，它涉及到在电路板或集成电路上安排和连接电子元件的过程。这个过程的目标是在满足电气性能、信号完整性、电磁兼容性等要求的同时，实现对空间、成本和生产工艺的优化。 ![](https://cdn.luogu.com.cn/upload/image_hosting/vcbssp42.png)","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGB3791"},"statements":[{"statement_type":"Markdown","content":"电路布局布线（Circuit Layout and Routing）是电子设计自动化（EDA）领域的一个重要概念，它涉及到在电路板或集成电路上安排和连接电子元件的过程。这个过程的目标是在满足电气性能、信号完整性、电磁兼容性等要求的同时，实现对空间、成本和生产工艺的优化。\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/vcbssp42.png)\n\n小小现在需要解决一个简化的电路布线问题，在一个 $n × m$ 的方格中进行电路布线。其中：\n- 井号 `#` 标记的格子已经被占用，不能布线。\n- 加号 `+` 标记的格子会连接到电路的其他部分，必须被布线。在给定的电路布线问题中，至少有一个格子必须被布线。\n- 点号 `.` 标记的格子小小有权选择是否布线：布线即将该格标记为加号，不布线即保持为点号。\n\n小小的任务是选择尽可能多的格子进行布线 (将 `.` 的格子标记为 `+`)，满足：\n1. 布线电路连通。即从任意一个已布线的格子，都能通过上、下、左、右移动到相邻已布线格子的方式，到达任意另一个布线的格子。\n2. 布线不存在短路 (回路)，即不存在某个布线的格子能通过 $> 2$ 步的上、下、左、右移动到相邻布线格子的方式回到自身，且经过的格子各不相同。\n\n例如，以下是一个电路布线问题，已有三个格子被标记为必须布线 (加号)：\n```plain\n#....#\n....+#\n.+####\n.+...#\n```\n以下展示了一种合法和两种不合法的布线方案：\n```plain\n#+.+.# #.+..# #++..#\n+++++# ..+++# .++++#\n.+#### .+#### .+####\n.++++# .+...# .+...#\n合法 不连通 有回路\n```\n\n## Input\n\n输入第一行是两个空格分隔的整数 $n$ 和 $m$，代表布线问题格子的行数和列数。\n\n接下来 $n$ 行，每行 $m$ 个字符（`#`、`+`、`.` 中的一个），描述了具体的布线问题。\n\n输入数据保证至少存在一种合法的布线方案。输入数据中至少有一个 `+`。\n\n## Output\n\n输出 $n$ 行，每行 $m$ 个字符，代表最优的布线方案，其中被布线的格子尽可能多。如有多种可能的方案，输出任意一种即可。\n\n[samples]\n\n## Note\n\n### 数据规模\n\n对于 $40\\%$ 的数据，满足 $n × m \\le 16$。\n\n对于 $100\\%$ 的数据，满足 $1\\le n, m \\le 6$。\n\n### 评分标准\n\n在你的布线方案合法（连通且无回路）的前提下：\n\n- 如果你的方案是最优布线方案，即布线的格子最多，该测试点得满分。\n- 否则，该测试点得一半分数。\n\n>本题原始满分为 $20\\text{pts}$。\n\n---\n\nSPJ Provider：@[scp020](https://www.luogu.com.cn/user/553625)","is_translate":false,"language":"English"}],"meta":{"iden":"LGB3791","tags":["动态规划 DP","搜索","2023","江苏","Special Judge","剪枝","折半搜索 meet in the middle","信息与未来"],"sample_group":[["2 2\n+.\n..","+.\n++"],["3 5\n...+#\n..###\n....+","++++#\n.+###\n+++++"],["5 6\n..++..\n.#..#.\n.#..#.\n.#..#.\n......","++++++\n+#.+#+\n+#+.#+\n+#++#+\n++.+++"]],"created_at":"2026-03-03 11:09:25"}}