题目描述
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$.
题意概述
给定一张$n \times m$的有障碍矩阵,其中恰有两个2和两个3,其余有些格子上有障碍。求分别连接两个2和两个3的两条不相交路径长度之和的最小值。
数据范围:$1 \le n, m \le 9$。
算法分析
插头DP,维护一排插头,令$f_{i, j, s}$表示处理到第$i$行第$j$列的格子且插头的状态为$s$时的最小值,根据当前格子的状态进行相应的转移。
代码
#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; }