HDU 4856

http://acm.hdu.edu.cn/showproblem.php?pid=4856

西安邀请赛的一道题，这道题我们当时在现场最后1h才发现时状态压缩dp，惊险写出

现在回头想发现当时有点呆，这种明显tsp模型的题目当时鬼迷心窍去写搜索，超时而不知悔改，实际是水题一道

#include <iostream>

#include <map>

#include <cstdio>

#include <cstring>

#include <queue>

using namespace std ;

const int INF=0xfffffff ;

int n,m ;

char M[][] ;

int vis[][] ;

int dis[][] ;

int dx[]={,-,,} ;

int dy[]={,,,-} ;

int dp[][<<] ;//在管道i时，状态为s

struct node

{

    int x1,y1,x2,y2 ;

}kk[] ;

struct point

{

    int x,y,step ;

} ;

int bfs(node a,node b)

{

    memset(vis,,sizeof(vis)) ;

    queue <point> q ;

    point s ;

    s.x=a.x2 ;s.y=a.y2 ;s.step= ;

    vis[s.x][s.y]= ;

    q.push(s) ;

    while(!q.empty())

    {

        point u=q.front() ;

        q.pop() ;

        if(u.x==b.x1 && u.y==b.y1)

        {

            return u.step ;

        }

        for(int i= ;i< ;i++)

        {

            int xx=u.x+dx[i] ;

            int yy=u.y+dy[i] ;

            if(xx< || xx>=n || yy< || yy>=n)continue ;

            if(M[xx][yy]=='#')continue ;

            if(vis[xx][yy])continue ;

            vis[xx][yy]= ;

            point next ;

            next.x=xx ;next.y=yy ;next.step=u.step+ ;

            q.push(next) ;

        }

    }

    return INF ;

}

void INIT()

{

    for(int i= ;i< ;i++)

        for(int j= ;j< ;j++)

            dis[i][j]=INF ;

    for(int i= ;i<m ;i++)

    {

        for(int j= ;j<m ;j++)

        {

            if(i==j)

            {

                dis[i][j]= ;

                continue ;

            }

            dis[i][j]=bfs(kk[i],kk[j]) ;

        }

    }

}

int main()

{

    while(~scanf("%d%d",&n,&m))

    {

        for(int i= ;i<n ;i++)

            scanf("%s",M[i]) ;

        for(int i= ;i<m ;i++)

        {

            scanf("%d%d%d%d",&kk[i].x1,&kk[i].y1,&kk[i].x2,&kk[i].y2) ;

            kk[i].x1-- ;kk[i].y1-- ;kk[i].x2-- ;kk[i].y2-- ;

        }

        INIT() ;

        for(int i= ;i< ;i++)

            for(int j= ;j<(<<) ;j++)

                dp[i][j]=INF ;

        for(int i= ;i<m ;i++)dp[i][<<i]= ;

        int ans=INF ;

        for(int i= ;i<(<<m) ;i++)

        {

            for(int j= ;j<m ;j++)

            {

                if(i&(<<j))

                {

                    for(int k= ;k<m ;k++)

                    {

                        if(dis[k][j]==INF || !(i&(<<k)))continue ;

                        dp[j][i]=min(dp[j][i],dp[k][i^(<<j)]+dis[k][j]) ;

                    }

                }

            }

        }

        for(int i= ;i<m ;i++)

            ans=min(ans,dp[i][(<<m)-]) ;

        if(ans==INF)puts("-1") ;

        else printf("%d\n",ans) ;

    }

    return  ;

}