http://poj.org/problem?id=3133 (题目链接)
题意
$n*m$的网格里有空格和障碍，还有两个$2$和两个$3$。要求把这两个$2$和两个$3$各用一条折线连起来。障碍里不能有线，而每个空格里最多只能有一条线，也就是说两条折线不能相交，每条折线不能自交。问两条折线的总长度最短是多少。
Solution
插头dp。
类似于插头记录连通情况，我们这里的插头记录的是它属于那条折线。折线只有两条，所以插头的种类就三种：0(无插头)，2(插头所在的直线是$2$所延伸出的直线)，3(插头所在的直线是$3$所延伸出的直线)。所以我们用四进制记录状态，解码的时候也不需要求解最小表示法了。$f[i][j][k]$表示到了格子$(i,j)$，状态$k$的折线最短长度。前面两维滚动一下。
转移分三种情况：格子为障碍，格子为空格，格子为$2$或$3$。如果跟hash中的重复了就取个min好了。别的都跟那道板子题差不多。
细节
注意清空hash表。
代码
// poj3133
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define LL long long
#define MOD 4001
#define inf 2147483640
#define Pi acos(-1.0)
#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
using namespace std;
const int maxd=15,maxs=100010,maxh=4010;
int n,m,code[maxd],a[maxd][maxd];
int next[maxs],head[maxh];
int size[2],dis[2][maxs],s[2][maxs];
void decode(int st) {
for (int i=m;i>=0;i--) code[i]=st&3,st>>=2;
}
int encode() {
int st=0;
for (int i=0;i<=m;i++) st=st<<2|code[i];
return st;
}
void add(int p,int d) {
int tmp=encode(),id=tmp%MOD;
for (int i=head[id];i;i=next[i])
if (s[p][i]==tmp) {dis[p][i]=min(dis[p][i],d);return;}
dis[p][++size[p]]=d;s[p][size[p]]=tmp;
next[size[p]]=head[id];head[id]=size[p];
}
void shift() {
for (int i=m;i;i--) code[i]=code[i-1];code[0]=0;
}
int main() {
while (scanf("%d%d",&n,&m)!=EOF && n && m) {
memset(a,0,sizeof(a));
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++) {
scanf("%d",&a[i][j]);
if (a[i][j]==0 || a[i][j]==1) a[i][j]^=1;
}
int p=0;
size[p]=1;dis[p][1]=0;s[p][1]=0;
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++) {
size[p^=1]=0;
memset(head,0,sizeof(head));
for (int k=1;k<=size[p^1];k++) {
decode(s[p^1][k]);
int left=code[j-1],up=code[j];
if (a[i][j]==0) {
code[j-1]=code[j]=0;
if (j==m) shift();
add(p,dis[p^1][k]);
}
else if (a[i][j]==1) {
if (left && up) {
if (left==up) {
code[j-1]=code[j]=0;
if (j==m) shift();
add(p,dis[p^1][k]+1);
}
}
else if (left || up) {
int tmp=left ? left : up;
if (a[i][j+1]) {
code[j-1]=0,code[j]=tmp;
add(p,dis[p^1][k]+1);
}
if (a[i+1][j]) {
code[j-1]=tmp,code[j]=0;
if (j==m) shift();
add(p,dis[p^1][k]+1);
}
}
else {
if (a[i+1][j] && a[i][j+1]) {
code[j-1]=code[j]=2;
add(p,dis[p^1][k]+1);
code[j-1]=code[j]=3;
add(p,dis[p^1][k]+1);
}
code[j-1]=code[j]=0;
if (j==m) shift();
add(p,dis[p^1][k]);
}
}
else if (a[i][j]==2 || a[i][j]==3) {
if ((left && !up) || (up && !left)) {
int tmp=left ? left : up;
if (tmp==a[i][j]) {
code[j-1]=code[j]=0;
if (j==m) shift();
add(p,dis[p^1][k]);
}
}
else if (!left && !up) {
if (a[i][j+1]) {
code[j-1]=0,code[j]=a[i][j];
add(p,dis[p^1][k]);
}
if (a[i+1][j]) {
code[j-1]=a[i][j],code[j]=0;
if (j==m) shift();
add(p,dis[p^1][k]);
}
}
}
}
}
int ans=inf;
for (int i=1;i<=size[p];i++) ans=min(ans,dis[p][i]);
printf("%d
",ans==inf ? 0 : ans+2);
}
return 0;
}