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.

epsfbox{p3620.eps}

Figure 6: An example setting and its solution

Input 

The input consists of multiple datasets, each in the following format.

n    m
row1
$ vdots$
rown
n is the number of rows which satisfies 2$ le$n$ le$9. m is the number of columns which satisfies 2$ le$m$ le$9. 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;
}