2013-10-04 11:22:27Morris
[UVA][插頭DP] 1214 - Manhattan Wiring
There is a rectangular area containing n x 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. 6(a) shows an example setting. Fig. 6(b) shows two lines satisfying the constraints above with minimum total length 18.
Figure 6: An example setting and its solution
Input
The input consists of multiple datasets, each in the following format.
n is the number of rows which satisfies 2
n m row1 rown
n9.
m is the number of columns which satisfies
2m9.
Each rowi is a sequence of m digits separated by a space.
The digits mean the following.
- 0:
- Empty
- 1:
- Occupied by an obstacle
- 2:
- Marked with ``2''
- 3:
- Marked with ``3''
The end of the input is indicated with a line containing two zeros separated by a space.
Output
For each dataset, one line containing the minimum total length of the two lines should be output. If there is no pair of lines satisfying the requirement, answer ``0'' instead. No other characters should be contained in the output.
Sample Input
5 5 0 0 0 0 0 0 0 0 3 0 2 0 2 0 0 1 0 1 1 1 0 0 0 0 3 2 3 2 2 0 0 3 3 6 5 2 0 0 0 0 0 3 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 2 3 0 5 9 0 0 0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 2 0 0 0 0 0 2 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 9 9 3 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 3 9 9 0 0 0 1 0 0 0 0 0 0 2 0 1 0 0 0 0 3 0 0 0 1 0 0 0 0 2 0 0 0 1 0 0 0 0 3 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 9 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 3 2 0 0
Sample Output
18 2 17 12 0 52 43
[ICPC2006日本橫濱] Manhattan Wiring
POJ3133、UVA1214、ZOJ2823、Aizu1270、LA3620。
題目描述：
一個兩個指定不相交路徑的起始與終點。
並且求最少路徑總和，類似一款 APP 遊戲將相同顏色的點連線，其中不會產生共同交點。
題目討論：
一開始以為可以用最少費用流去解，但是基於要相同顏色互連下，最少費用流的解可能會連錯，因此這種考慮方式無法解決。由於盤面限制在 h x w (h, w < 10)，也許可以 brute force+cut。
但最後使用"插頭DP"解決，插頭DP另一個稱呼是"輪廓線"，根據順序將輪廓線轉移，而輪廓線上的所有點要壓縮成一個狀態。之前學過的插頭DP大多是迴路計算，而這題會使用到獨立插頭，也就是一個單獨路徑的開始。
此題由於有兩個指定使用，因此將狀態壓縮成 3 進制，0 無任何插頭，1 二號專用插頭，2 三號專用插頭。而在寫程式為了加速考慮，使用 4 進制較為快速，0 無任何插頭，2 二號專用插頭，3 三號專用插頭。而由於無用的狀態轉移相當多，編寫時使用 HASH 加速，用手寫一個內存池的版本較為適用。
總之，寫這題 DP 時，考慮的轉移狀態相當多，面對獨立插頭設計時，特別考慮是路徑的起點，以免造成通過自己而沒抵達終點的迴路。
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int g[15][15], n, m;
struct Node {
int first, second;
Node(int a=0, int b=0):
first(a), second(b) {}
};
struct HASH {
#define HSIZE 10007
#define HNODE 1048576
int head[HSIZE], next[HNODE], nsize;
Node nd[HNODE];
void init() {
memset(head, -1, sizeof(head));
nsize = 0;
}
void add(int hidx, Node s) {
nd[nsize] = s;
next[nsize] = head[hidx];
head[hidx] = nsize;
nsize++;
}
void update(Node s) {
static int hidx, i;
hidx = s.first%HSIZE;
for(i = head[hidx]; i != -1; i = next[i]) {
if(nd[i].first == s.first) {
nd[i].second = min(nd[i].second, s.second);
return;
}
}
add(hidx, s);
}
};
HASH dp[2];
//4 state: '0' empty, '2': 2 used plug, '3': 3 used plug.
void dpEmpty(int i, int j, int flag) {
int cost, k, left, up;
int nstate;
int ptr;
for(ptr = dp[flag].nsize-1; ptr >= 0; ptr--) {
k = dp[flag].nd[ptr].first, cost = dp[flag].nd[ptr].second;
left = (k>>(2*j))&3, up = (k>>(2*(j+1)))&3;
if(left && up) {// two plus, link left&up
if(left != up) continue;
nstate = k^(left<<(2*j))^(up<<(2*(j+1)));
if(j == m-1) nstate <<= 2;
dp[!flag].update(Node(nstate, cost+1));
} else if(left) {// only one left plus
if(g[i][j+1] == 0 || g[i][j+1] == left) {//left-to-right
nstate = k^(left<<(2*j))|(left<<(2*(j+1)));
dp[!flag].update(Node(nstate, cost+1));
}
if(g[i+1][j] == 0 || g[i+1][j] == left) {//left-to-down
nstate = k^(up<<(2*(j+1)));
if(j == m-1) nstate <<= 2;
dp[!flag].update(Node(nstate, cost+1));
}
} else if(up) {// only one up plus
if(g[i][j+1] == 0 || g[i][j+1] == up) {//up-to-right
nstate = k^(left<<(2*j));
dp[!flag].update(Node(nstate, cost+1));
}
if(g[i+1][j] == 0 || g[i+1][j] == up) {//up-to-down
nstate = k^(up<<(2*(j+1)))|(up<<(2*j));
if(j == m-1) nstate <<= 2;
dp[!flag].update(Node(nstate, cost+1));
}
} else {
// non-place.
nstate = k;
if(j == m-1) nstate <<= 2;
dp[!flag].update(Node(nstate, cost));
// place
if((g[i][j+1] == 0 && g[i+1][j] == 0) || (g[i+1][j] == 2 && g[i][j+1] == 2) ||
(g[i+1][j] == 2 && g[i][j+1] == 0) || (g[i+1][j] == 0 && g[i][j+1] == 2)) {// make 2-used path
nstate = k|(2<<(2*j))|(2<<(2*(j+1)));
dp[!flag].update(Node(nstate, cost+1));
}
if((g[i][j+1] == 0 && g[i+1][j] == 0) || (g[i+1][j] == 3 && g[i][j+1] == 3) ||
(g[i+1][j] == 3 && g[i][j+1] == 0) || (g[i+1][j] == 0 && g[i][j+1] == 3)) {// make 3-used path
nstate = k|(3<<(2*j))|(3<<(2*(j+1)));
dp[!flag].update(Node(nstate, cost+1));
}
}
}
}
void dpObstacle(int i, int j, int flag) {
int cost, k, left, up;
int nstate;
int ptr;
for(ptr = dp[flag].nsize-1; ptr >= 0; ptr--) {
k = dp[flag].nd[ptr].first, cost = dp[flag].nd[ptr].second;
left = (k>>(2*j))&3, up = (k>>(2*(j+1)))&3;
if(left || up) continue;// should not have plug.
nstate = k;
if(j == m-1) nstate <<= 2;
dp[!flag].update(Node(nstate, cost));
}
}
void dp2(int i, int j, int flag) {
int cost, k, left, up;
int nstate;
int ptr;
for(ptr = dp[flag].nsize-1; ptr >= 0; ptr--) {
k = dp[flag].nd[ptr].first, cost = dp[flag].nd[ptr].second;
left = (k>>(2*j))&3, up = (k>>(2*(j+1)))&3;
if(left && up) continue;// should not have two plug.
if(left && left != 2) continue;// should have plug of '2'.
if(up && up != 2) continue;// should have plug of '2'.
if(left || up) {// link this plug.
nstate = k^(left<<(2*j))^(up<<(2*(j+1)));
if(j == m-1) nstate <<= 2;
dp[!flag].update(Node(nstate, cost+1));
} else {// no plug, build new plug.
if(g[i][j+1] == 0 || g[i][j+1] == 2) {// to-right
nstate = k|(2<<(2*(j+1)));
dp[!flag].update(Node(nstate, cost+1));
}
if(g[i+1][j] == 0 || g[i+1][j] == 2) {// to-down
nstate = k|(2<<(2*j));
if(j == m-1) nstate <<= 2;
dp[!flag].update(Node(nstate, cost+1));
}
}
}
}
void dp3(int i, int j, int flag) {
int cost, k, left, up;
int nstate;
int ptr;
for(ptr = dp[flag].nsize-1; ptr >= 0; ptr--) {
k = dp[flag].nd[ptr].first, cost = dp[flag].nd[ptr].second;
left = (k>>(2*j))&3, up = (k>>(2*(j+1)))&3;
//if(dp[flag][k] != oo) printf("%d %d\n", k, dp[flag][k]);
if(left && up) continue;// should not have two plug.
if(left && left != 3) continue;// should have plug of '3'.
if(up && up != 3) continue;// should have plug of '3'.
if(left || up) {// link this plug.
nstate = k^(left<<(2*j))^(up<<(2*(j+1)));
if(j == m-1) nstate <<= 2;
dp[!flag].update(Node(nstate, cost+1));
} else {// no plug, build new plug.
if(g[i][j+1] == 0 || g[i][j+1] == 3) {// to-right
nstate = k|(3<<(2*(j+1)));
dp[!flag].update(Node(nstate, cost+1));
}
if(g[i+1][j] == 0 || g[i+1][j] == 3) {// to-down
nstate = k|(3<<(2*j));
if(j == m-1) nstate <<= 2;
dp[!flag].update(Node(nstate, cost+1));
}
}
}
}
void DP(int n, int m) {
int i, j, k, ptr;
int flag = 0;
dp[0].init();
dp[0].update(Node(0, 0));
for(i = 0; i < n; i++) {
for(j = 0; j < m; j++) {
dp[!flag].init();
if(g[i][j] == 0) dpEmpty(i, j, flag);
else if(g[i][j] == 1) dpObstacle(i, j, flag);
else if(g[i][j] == 2) dp2(i, j, flag);
else if(g[i][j] == 3) dp3(i, j, flag);
flag = !flag;
}
}
int ret = 0;
for(ptr = dp[flag].nsize-1; ptr >= 0; ptr--) {
if(dp[flag].nd[ptr].first == 0) {
ret = dp[flag].nd[ptr].second;
}
}
if(ret > 2) ret -= 2;
printf("%d\n", ret);
}
int main() {
int i, j, k;
while(scanf("%d %d", &n, &m) == 2 && n+m) {
for(i = 0; i <= n; i++)
for(j = 0; j <= m; j++)
g[i][j] = 1;//obstacle
for(i = 0; i < n; i++)
for(j = 0; j < m; j++)
scanf("%d", &g[i][j]);
DP(n, m);
}
return 0;
}