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;  
}