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$.

题意概述

给定一张$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;
}