poj 3133 Manhattan Wiring 插头dp
插头dp 这个题目还是比较直接的，就是转移比较麻烦，要先考虑格子的三种情况，然后分别讨论转移情况。
不过我认为用启发式搜索应该是可以更加直接有效的过这题。
有时间再试试启发式。
#include <iostream>#include <cstdio>#include <cstring>using namespace std;const int maxn=10,maxm=2e4+9;int a[maxn][maxn];int n,m;struct{ int hash[maxm],lon; struct { int key,dist,next; }data[maxm]; void clear() { memset(hash,-1,sizeof(hash)); lon=0; } void push(int key,int dist) {// prin(key); int tmp=key%maxm; for(int k=hash[tmp];k!=-1;k=data[k].next) if(data[k].key==key) { data[k].dist=min(data[k].dist,dist); return ; } data[++lon].dist=dist; data[lon].key=key; data[lon].next=hash[tmp]; hash[tmp]=lon; }}dp[2];inline int getbit(int key,int t){ key=key&(3<<t*2); key=key>>t*2; return key;}inline int movbit(int key,int j){ key=key<<j*2; return key;}void solve(){ int pre=1,now=0; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { pre=pre^1,now=now^1; dp[now].clear(); if(i==1&&j==1) { dp[pre].clear(); dp[pre].push(0,0); }// cout<<dp[pre].lon<<endl; for(int k=1;k<=dp[pre].lon;k++) { int key=dp[pre].data[k].key; int dist=dp[pre].data[k].dist; int down=getbit(key,j); int r=getbit(key,0); if(a[i][j]==2||a[i][j]==3) { if(down==a[i][j]&&r==0) { dp[now].push(key-movbit(down,j),dist+1); } else if(down==0&&r==a[i][j]) { dp[now].push(key-r,dist+1); } else if(down==0&&r==0) { if(j!=m) dp[now].push(key+a[i][j],dist+1); if(i!=n) dp[now].push(key+movbit(a[i][j],j),dist+1); } } else if(a[i][j]==1) { if(!down&&!r) dp[now].push(key,dist); } else if(a[i][j]==0) { if(!down&&!r) { for(int txt=2;txt<=3;txt++) { if(i!=n&&j!=m) dp[now].push(key+movbit(txt,j)+txt,dist+1); } dp[now].push(key,dist); } else if(down&&!r) { if(j!=m) dp[now].push(key-movbit(down,j)+down,dist+1); if(i!=n) dp[now].push(key,dist+1); } else if(!down&&r) { if(j!=m) dp[now].push(key,dist+1); if(i!=n) dp[now].push(key-r+movbit(r,j),dist+1); } else if(down&&r) { if(down==r) dp[now].push(key-r-movbit(down,j),dist+1); } } } } bool flag=false; for(int i=1;i<=dp[now].lon;i++) if(dp[now].data[i].key==0) { cout<<dp[now].data[i].dist-2<<endl; flag=true; } if(!flag) cout<<0<<endl;}int main(){// freopen("in.txt","r",stdin); while(scanf("%d %d",&n,&m),n||m) { for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&a[i][j]); solve(); } return 0;}