题解：B3791 [信息与未来 2023] 电路布线

wsy_I · 2026-11-08 20:01:26 · 题解

神秘搜索题。下文认为 n,m 同阶。由于我太懒只写了 solution 1 的代码。

::::info[solution 1]

一个渐进复杂度错误但是卡不掉的方法。

一个显然的暴力是，枚举每一个空白格子放不放电线，最后判断方案是否合法，这样是 O(n^22^{n^2}) 的，显然过不去。

使用鬼脑尝试剪枝，会发现有以下三个比较显然的剪枝：

• 最优性剪枝，假如当前填 + 的格子数量加上没搜索的所有格子数量都比目前搜出的最优答案劣，那么肯定不会成为最优答案。
• 可行性剪枝，假如当前格子填 + 会形成回路就不能搜 +。
• 优化搜索顺序，把一个格子优先尝试填 +，否则填 .，这样可以让你第一次搜到的答案比较大，使得最优性剪枝更强。

由于不优化搜索顺序搜出来正好和样例一样，我们大胆猜测 std 并没有用优化搜索顺序，发现不用这个优化确实能过，但是最大点从 26 毫秒变成了 210 毫秒。下面是使用全部优化的代码：

#include <bits/stdc++.h>
#define rep(i, l, r) for(int i = (l); i <= (r); i ++ )
#define per(i, l, r) for(int i = (l); i >= (r); i -- )
#define endl '\n'
using namespace std;

const int N = 6 + 5;
int n, m, ans, d[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
bool vis[N][N];
char ch[N][N], anm[N][N];

bool getloop(int x, int y, int px, int py) {
  vis[x][y] = true;
  bool flag = false;
  rep(i, 0, 3) {
    int dx = x + d[i][0], dy = y + d[i][1];
    if(dx > n || dy > m || dx < 1 || dy < 1 || ch[dx][dy] != '+') continue;
    if(dx == px && dy == py) continue;
    if(vis[dx][dy]) return true;
    flag |= getloop(dx, dy, x, y);
  }
  return flag;
}

void dfs(int x, int y, int dis) {
  if(x == n + 1) {
    if(dis > ans) {
      ans = dis;
      memcpy(anm, ch, sizeof anm);
    }
    return;
  }
  if(dis + m * (n - x) + m - y < ans) return;
  int nx, ny;
  if(y == m) nx = x + 1, ny = 1;
  else nx = x, ny = y + 1;
  if(ch[x][y] == '#') {
    dfs(nx, ny, dis);
    return;
  } else if(ch[x][y] == '+') {
    memset(vis, false, sizeof vis);
    if(getloop(x, y, 0, 0)) return;
    dfs(nx, ny, dis + 1);
  } else {
    ch[x][y] = '+';
    memset(vis, false, sizeof vis);
    if(!getloop(x, y, 0, 0)) dfs(nx, ny, dis + 1);
    ch[x][y] = '.';
    dfs(nx, ny, dis);
  }
}

int main() {
  ios :: sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  cin >> n >> m;
  rep(i, 1, n) rep(j, 1, m) cin >> ch[i][j];
  dfs(1, 1, 0);
  rep(i, 1, n) {
    rep(j, 1, m) cout << anm[i][j];
    cout << endl;
  }
  return 0;
}

::::

::::info[solution 2] 一个复杂度正确的做法，轮廓线 DP。复杂度 O(n^2n^n)。首先注意到插入一个数只和左边和上面的数有关，所以可以只记录轮廓线进行转移。

略去轮廓线 DP 的基本知识。设 dp_{x,y,S} 表示 (x,y) 这个节点，轮廓线为 S 的时候，前面能够填的最多 + 数量以及方案。这里是回路问题，使用最小表示法。

那么对于插头进行分类讨论。

• 下插头和右插头都没有。假如这个点选择 +，那只能新开一个连通块，向左向下插一个插头；否则两边都没有插头。
• 左插头和右插头只有一个。那么，假如这个点选择 +，那么继承插到它的插头方向；否则没有插头。
• 左插头和右插头都有。假如左插头和右插头是同一个连通块的，那么这个点不能选择 +；否则选择 + 的时候合并两个连通块，没有插头。