# Manhattan Wiring

## 题目描述

There is a rectangular area containing $n \times m$ cells. Two cells are marked with “2”, and another two with “3”. Some cells are occupied by obstacles. You should connect the two “2”s and also the two “3”s with non-intersecting lines. Lines can run only vertically or horizontally connecting centers of cells without obstacles.
Lines cannot run on a cell with an obstacle. Only one line can run on a cell at most once. Hence, a line cannot intersect with the other line, nor with itself. Under these constraints, the total length of the two lines should be minimized. The length of a line is defined as the number of cell borders it passes. In particular, a line connecting cells sharing their border has length $1$.
Fig. 1(a) shows an example setting. Fig. 1(b) shows two lines satisfying the constraints above with minimum total length $18$.

## 代码

#include <cstdio>
#include <cstring>

void minify(short &a, short b) {
a > b && (a = b);
}

static const int N = 11;
int rec[1 << 20];
short mp[N][N], f[2][N][1 << 20]; // 0 for no wire, 2 for wire 2, 3 for wire 3

int modify(int s, int p, int v) {
return (s & ((1 << (p << 1)) - 1)) | (((s >> ((p + 1) << 1) << 2) + v) << (p << 1));
}

int query(int s, int p) {
return s >> (p << 1) & 3;
}

int main() {
int n, m, top = 0;
for (int i = 0; i < 1 << 20; ++ i) {
for (int j = 0; j < N; ++ j) if (query(i, j) == 1) goto illegal;
rec[top ++] = i; illegal: ;
}
while (scanf("%d%d", &n, &m), n) {
for (int i = 0; i < n; ++ i)
for (int j = 0; j < m; ++ j) scanf("%hd", &mp[i][j]);
int cur = 0; memset(f, 0x3f, sizeof f), f[cur][0][0] = 0;
for (int i = 0; i < n; ++ i, cur ^= 1) {
for (int j = 0; j < m; ++ j)
for (int _ = 0, k = rec[0]; _ < top; k = rec[++ _])
if (f[cur][j][k] < 10000) {
int p = query(k, j), q = query(k, j + 1);
if (mp[i][j] == 0) {
if (! p && ! q)
minify(f[cur][j + 1][k], f[cur][j][k]),
minify(f[cur][j + 1][modify(modify(k, j, 2), j + 1, 2)], f[cur][j][k] + 1),
minify(f[cur][j + 1][modify(modify(k, j, 3), j + 1, 3)], f[cur][j][k] + 1);
else if (! p ^ ! q)
minify(f[cur][j + 1][modify(modify(k, j, p + q), j + 1, 0)], f[cur][j][k] + 1),
minify(f[cur][j + 1][modify(modify(k, j, 0), j + 1, p + q)], f[cur][j][k] + 1);
else if (p && p == q)
minify(f[cur][j + 1][modify(modify(k, j, 0), j + 1, 0)], f[cur][j][k] + 1);
} else if (mp[i][j] == 1) {
if (! p && ! q) minify(f[cur][j + 1][k], f[cur][j][k]);
} else {
if (! p && ! q)
minify(f[cur][j + 1][modify(k, j, mp[i][j])], f[cur][j][k] + 1),
minify(f[cur][j + 1][modify(k, j + 1, mp[i][j])], f[cur][j][k] + 1);
else if (p == mp[i][j] && ! q)
minify(f[cur][j + 1][modify(k, j, 0)], f[cur][j][k] + 1);
else if (! p && q == mp[i][j])
minify(f[cur][j + 1][modify(k, j + 1, 0)], f[cur][j][k] + 1);
}
}
for (int _ = 0, k = rec[0]; _ < top; k = rec[++ _])
if (! query(k, m)) minify(f[cur ^ 1][0][k << 2 & (1 << ((m + 1) << 1)) - 1], f[cur][m][k]);
for (int j = 0; j <= m; ++ j)
for (int _ = 0, k = rec[0]; _ < top; k = rec[++ _]) f[cur][j][k] = 16000;
}
printf("%d\n", f[cur][0][0] < 10000 ? f[cur][0][0] - 2 : 0);
}
return 0;
}

418 I'm a teapot