设为首页 加入收藏

TOP

HDU 4856 Tunnels （最短路+状压DP）
2015-07-24 05:36:45 来源: 作者: 【大 中 小】 浏览:5次
Tags：HDU 4856 Tunnels 短路 状压



题意：给你N*N的网格，‘.’表示可以走，‘#’表示不能走，m条管道，每条管道有起点和终点坐标，


Bob每次可以走到相邻的网格花费1s，问Bob走完m条管道要花多少时间；Bob在管道内不计算时间


即计算Bob从管道 i 的出口走到管道 j 的入口的时间Dis(e[i],s[j])的最小和，起点可以任意；


思路：看了题解说是状态压缩DP然后深入理解了下。


首先算出d[e[i]][s[j]]的最短距离，不能到达为-1；


dp[i][j] : 表示以 j 为起点状态为 i 的最小值。其中 i 是用十进制表示的二进制，


eg：

dp[5][2]：5的二进制位101，表示以编号2管道为起点（0~m-1），走了0,2号管道的最小值。


#include
  
   
#include
   
     #include
    
      #include
      #include
      
        #include
       
         #include
        
          #include
         
           #include
          
            #include
           
             #include
            
              using namespace std; #define maxn 20 struct Point { int x,y; int sum; }; int n,m,g[maxn][maxn],ans,vis[maxn]; int ma[maxn][maxn]; char str[maxn][maxn]; Point s[maxn],e[maxn]; int dir[4][2]={{-1,0},{0,1},{0,-1},{1,0}}; int d[maxn][maxn]; int OK(int a,int b) { if(a<1||a>n||b<1||b>n||g[a][b]==-1) return 0; return 1; } int dis(Point s,Point e) { queue
             
              q; Point u,v; s.sum=0; q.push(s); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) g[i][j]=ma[i][j]; g[s.x][s.y]=-1; while(!q.empty()) { u=q.front(); q.pop(); if(u.x==e.x&&u.y==e.y) { return u.sum; } for(int i=0;i<4;i++) { v.x=u.x+dir[i][0]; v.y=u.y+dir[i][1]; if(OK(v.x,v.y)) { g[v.x][v.y]=-1; v.sum=u.sum+1; q.push(v); } } } return -1; } int dp[1<<15][maxn]; int main() { while(~scanf("%d%d",&n,&m)) { int i,j,k; for(i=1;i<=n;i++) { scanf("%s",str[i]+1); for(j=1;j<=n;j++) { if(str[i][j]=='.') ma[i][j]=1; else ma[i][j]=-1; } } for(i=0;i
              
               dp[M-1][i]) ans=dp[M-1][i]; } printf("%d\n",ans); } return 0; } /* 5 4 ....# ...#. ..... ..... ..... 2 3 1 4 1 2 3 5 2 3 3 1 5 4 2 1 */


【大 中 小】【打印】 【繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部】
分享到: 
上一篇：hdu 4850 Wow! Such String!(欧拉.. 下一篇：Codeforces Round #254 (Div. 2)

评论

帐　　号: 密码: (新用户注册)
验 证 码:
表　　情:
内　　容: