信息与未来 2023 电路布线（暂无 SPJ）

题目描述

电路布局布线（Circuit Layout and Routing）是电子设计自动化（EDA）领域的一个重要概念，它涉及到在电路板或集成电路上安排和连接电子元件的过程。这个过程的目标是在满足电气性能、信号完整性、电磁兼容性等要求的同时，实现对空间、成本和生产工艺的优化。

小小现在需要解决一个简化的电路布线问题，在一个 n × m 的方格中进行电路布线。其中：

• 井号 '#' 标记的格子已经被占用，不能布线。
• 加号 '+' 标记的格子会连接到电路的其他部分，必须被布线。在给定的电路布线问题中，至少有一个格子必须被布线。
• 点号 '.' 标记的格子小小有权选择是否布线：布线即将该格标记为加号，不布线即保持为点号。

小小的任务是选择尽可能多的格子进行布线 (将 '.' 的格子标记为 '+')，满足：

1. 布线电路连通。即从任意一个已布线的格子，都能通过上、下、左、右移动到相邻已布线格子的方式，到达任意另一个布线的格子。
2. 布线不存在短路 (回路)，即不存在某个布线的格子能通过 > 2 步的上、下、左、右移动到相邻布线格子的方式回到自身，且经过的格子各不相同。

例如，以下是一个电路布线问题，已有三个格子被标记为必须布线 (加号)：

#....#
....+#
.+####
.+...#

以下展示了一种合法和两种不合法的布线方案：

#+.+.# #.+..# #++..#
+++++# ..+++# .++++#
.+#### .+#### .+####
.++++# .+...# .+...#
合法 不连通 有回路

输入格式

输入第一行是两个空格分隔的整数 n 和 m，代表布线问题格子的行数和列数。

接下来 n 行，每行 m 个字符（'#'、'+'、'.' 中的一个），描述了具体的布线问题。

输入数据保证至少存在一种合法的布线方案。输入数据中至少有一个 '+'.

输出格式

输出 n 行，每行 m 个字符，代表最优的布线方案，其中被布线的格子尽可能多。如有多种可能的方案，输出任意一种即可。

样例 #1

样例输入 #1

2 2
+.
..

样例输出 #1

+.
++

样例 #2

样例输入 #2

3 5
...+#
..###
....+

样例输出 #2

++++#
.+###
+++++

样例 #3

样例输入 #3

5 6
..++..
.#..#.
.#..#.
.#..#.
......

样例输出 #3

++++++
+#.+#+ 
+#+.#+
+#++#+
++.+++

提示

数据规模

对于 40% 的数据，满足 n × m ≤ 16。

对于 100% 的数据，满足 1 ≤ n, m ≤ 6。

评分标准

在你的布线方案合法（连通且无回路）的前提下：

• 如果你的方案是最优布线方案，即布线的格子最多，该测试点得满分。
• 否则，该测试点得一半分数。

本题原始满分为 20 pts。 用C++内容：```cpp #include #include #include #include

using namespace std;

const int MAXN = 6;

struct Point { int x, y; Point(int _x = 0, int _y = 0): x(_x), y(_y) {} };

int n, m; char grid[MAXN][MAXN]; int visited[MAXN][MAXN]; vector sources; int dx[4] = {0, 0, -1, 1}; int dy[4] = {-1, 1, 0, 0};

void bfs(int x, int y) { memset(visited, 0, sizeof(visited)); queue q; q.push(Point(x, y)); visited[x][y] = 1; while (!q.empty()) { Point p = q.front(); q.pop(); for (int i = 0; i < 4; i++) { int nx = p.x + dx[i]; int ny = p.y + dy[i]; if (nx >= 0 && nx < n && ny >= 0 && ny < m && grid[nx][ny] != '#' && visited[nx][ny] == 0) { q.push(Point(nx, ny)); visited[nx][ny] = 1; } } } }

int countConnected() { int count = 0; for (int i = 0; i < sources.size(); i++) { bfs(sources[i].x, sources[i].y); for (int j = 0; j < n; j++) { for (int k = 0; k < m; k++) { if (visited[j][k] == 1) { count++; } } } } return count; }

bol isValid() { int count = countConnected(); if (count == (n * m)) { return true; } return false; }

void dfs(int x, int y, int& maxCount) { if (x == n) { int count = countConnected(); if (count > maxCount && isValid()) { maxCount = count; } return; } if (y == m) { dfs(x + 1, 0, maxCount); return; } if (grid[x][y] == '.') { grid[x][y] = '+'; dfs(x, y + 1, maxCount); grid[x][y] = '.'; } dfs(x, y + 1, maxCount); }

int main() { cin >> n >> m; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cin >> grid[i][j]; if (grid[i][j] == '+') { sources.push_back(Point(i, j)); } } } int maxCount = 0; dfs(0, 0, maxCount); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cout << grid[i][j]; } cout << endl; } return 0; }