考虑插头 dp
用四进制表示一个插头的状态，0 表示没有插头，2 表示这个插头是连接两个 2 的，3 同理
然后就是大力分类讨论了
这题还是比较友善的一题，思路相对来说简单很多
我写的括号序列的方法状态是满的，数组必须开到 $ 3 ^ 9 $ 才能过
#include#include #include #define CIOS ios::sync_with_stdio(false);#define rep(i, a, b) for(register int i = a; i <= b; i++)#define per(i, a, b) for(register int i = a; i >= b; i--)#define DEBUG(x) cerr << "DEBUG" << x << " >>> ";using namespace std;typedef unsigned long long ull;typedef long long ll;template inline void read(T &f) { f = 0; T fu = 1; char c = getchar(); while(c < '0' || c > '9') { if(c == '-') fu = -1; c = getchar(); } while(c >= '0' && c <= '9') { f = (f << 3) + (f << 1) + (c & 15); c = getchar(); } f *= fu;}template void print(T x) { if(x < 0) putchar('-'), x = -x; if(x < 10) putchar(x + 48); else print(x / 10), putchar(x % 10 + 48);}template void print(T x, char t) { print(x); putchar(t);}const int mod = 19687, N = mod + 50, INF = 0x7fffffff;int a[15][15], bin[15], f[2][N], v[2][N], head[N], tot[2], nxt[N], n, m, now;// 状态只有 0, 2, 3, 表示没有插头, 2 插头和 3 插头 void ins(int zt, int val) { int u = zt % mod; for(register int i = head[u]; i; i = nxt[i]) if(v[now][i] == zt) { f[now][i] = min(f[now][i], val); return; } nxt[++tot[now]] = head[u]; head[u] = tot[now]; v[now][tot[now]] = zt; f[now][tot[now]] = val;}void sol() { tot[now] = 1; f[now][1] = v[now][1] = 0; for(register int i = 1; i <= n; i++) { for(register int i = 1; i <= tot[now]; i++) v[now][i] <<= 2; for(register int j = 1; j <= m; j++) { now ^= 1; memset(head, 0, sizeof(head)); tot[now] = 0; for(register int k = 1; k <= tot[now ^ 1]; k++) { int zt = v[now ^ 1][k], val = f[now ^ 1][k]; int left = (zt >> ((j << 1) - 2)) & 3, up = (zt >> (j << 1)) & 3; int right = (j == m) ? 1 : a[i][j + 1], down = (i == n) ? 1 : a[i + 1][j]; if(a[i][j] == 1) { if(!left && !up) ins(zt, val); } else if(!left && !up) { if(!a[i][j]) { ins(zt, val); if(right + down == 5 || right == 1 || down == 1) continue; if(right == 2 || down == 2) { // 当两边有 2 插头时, 向下和向右摆 2 插头 ins(zt ^ (bin[j - 1] << 1) ^ (bin[j] << 1), val + 1); } else if(right == 3 || down == 3) { ins(zt ^ (bin[j - 1] * 3) ^ (bin[j] * 3), val + 1); } else { ins(zt ^ (bin[j - 1] << 1) ^ (bin[j] << 1), val + 1); ins(zt ^ (bin[j - 1] * 3) ^ (bin[j] * 3), val + 1); } } else { // 当前位置是一个 2 或 3 if(a[i][j] + right != 5 && right != 1) { ins(zt ^ (bin[j] * a[i][j]), val + 1); } if(a[i][j] + down != 5 && down != 1) { ins(zt ^ (bin[j - 1] * a[i][j]), val + 1); } } } else if(left && up) { if(left + up == 5 || a[i][j]) continue; ins(zt ^ (bin[j - 1] * left) ^ (bin[j] * up), val + 1); } else if(left && !up) { if(a[i][j] == 0) { if(right == 0 || right == left) ins(zt ^ (bin[j - 1] * left) ^ (bin[j] * left), val + 1); if(down == 0 || down == left) ins(zt, val + 1); } else if(a[i][j] == left) { ins(zt ^ (bin[j - 1] * left), val + 1); } } else if(!left && up) { if(a[i][j] == 0) { if(right == 0 || right == up) ins(zt, val + 1); if(down == 0 || down == up) ins(zt ^ (bin[j] * up) ^ (bin[j - 1] * up), val + 1); } else if(a[i][j] == up) { ins(zt ^ (bin[j] * up), val + 1); } } } } }}int main() { bin[0] = 1; for(register int i = 1; i <= 11; i++) bin[i] = bin[i - 1] << 2; while(scanf("%d %d", &n, &m) == 2 && n && m) { memset(a, 0, sizeof(a)); memset(head, 0, sizeof(head)); memset(tot, 0, sizeof(tot)); for(register int i = 1; i <= n; i++) { for(register int j = 1; j <= m; j++) read(a[i][j]); } sol(); int ans = INF; for(register int i = 1; i <= tot[now]; i++) ans = min(ans, f[now][i]); if(ans == INF) ans = 2; print(ans - 2, '\n'); } return 0;}