HDU 4568 Hunter (状态压缩)

题目链接~~>

做题感悟：这题做了好几个小时，但是这题A的还算顺利没有什么坑。

解题思路：BFS + 优先队列+状态压缩

     （1）先用BFS+优先队列处理出各点到其他点和边界的最短路径。

     （2）用状态压缩枚举每种情况就ok了。

代码：

  

   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     

      #include<iomanip>
     
    
   

    

     

    
    

     

      #include<vector>
     
    
   

    

     

    
    

     

      #include<queue>
     
    
   

    

     

    
    

     

      #include<fstream>
     
    
   

    

     

    
    

     

      #include<string.h>
     
    
   

    

     

    
    

     

      #include<stdlib.h>
     
    
   

    

     

    
    

     

      #include<string.h>
     
    
   

    

     

    
    

     

      #include<algorithm>
     
    
   

    

     

    
    

     

      #include<iostream>
     
    
   

    

     

    
    

     

      #define INT long long int
     
    
   

    

     

    
    

     

      using namespace std ;
     
    
   

    

     

    
    

     

      const int INF = 999999999 ;
     
    
   

    

     

    
    

     

      const int MX = 200 + 10 ;
     
    
   

    

     

    
    

     

      const int MY = 15 ;
     
    
   

    

     

    
    

     

      int n,m,num ;
     
    
   

    

     

    
    

     

      bool vis[MX][MX] ;
     
    
   

    

     

    
    

     

      int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1} ;
     
    
   

    

     

    
    

     

      int a[MX],dg[MX],g[MX][MX],flag[MX][MX],d[MX][MX],dp[1<<14][14] ;
     
    
   

    

     

    
    

     

      struct node
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int x,y,step ;
     
    
   

    

     

    
    

     
 friend bool operator <(const node &a,const node &b)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 return a.step > b.step ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      } ;
     
    
   

    

     

    
    

     

      bool judge(int x,int y)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 if(x<0||y<0||x>=n||y>=m||vis[x][y]||g[x][y]==-1)
     
    
   

    

     

    
    

     
 return false ;
     
    
   

    

     

    
    

     
 return true ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int bfs(int x,int y)// BFS+优先队列求最短路
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int best=INF ;
     
    
   

    

     

    
    

     
 memset(vis,false,sizeof(vis)) ;
     
    
   

    

     

    
    

     
 priority_queue<node>q ;
     
    
   

    

     

    
    

     

       node curt,next ;
     
    
   

    

     

    
    

     

       curt.x=x ;
     
    
   

    

     

    
    

     

       curt.y=y ;
     
    
   

    

     

    
    

     

       curt.step=0 ;
     
    
   

    

     

    
    

     

       vis[x][y]=true ;
     
    
   

    

     

    
    

     

       q.push(curt) ;
     
    
   

    

     

    
    

     
 while(!q.empty())
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       curt=q.top() ;
     
    
   

    

     

    
    

     

       q.pop() ;
     
    
   

    

     

    
    

     
 if(flag[curt.x][curt.y]!=-1) // 此怪物与彼怪物的距离
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 int u = flag[x][y] ;
     
    
   

    

     

    
    

     
 int v=flag[curt.x][curt.y] ;
     
    
   

    

     

    
    

     

       d[u][v]=curt.step ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 if(!curt.x||!curt.y||curt.x==n-1||curt.y==m-1) // 求当前怪物点距离边界的最短距离
     
    
   

    

     

    
    

     

       best=min(best,curt.step) ;
     
    
   

    

     

    
    

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

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       next.x=curt.x+dx[i] ;
     
    
   

    

     

    
    

     

       next.y=curt.y+dy[i] ;
     
    
   

    

     

    
    

     
 if(judge(next.x,next.y))
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       next.step=curt.step+g[next.x][next.y] ;
     
    
   

    

     

    
    

     

       vis[next.x][next.y]=true ;
     
    
   

    

     

    
    

     

       q.push(next) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return best ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      void DP_SC() // 状态压缩
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 for(int S=0 ;S<(1<<num) ;S++)
     
    
   

    

     

    
    

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

    

     

    
    

     
 if(dp[S][i]!=-1)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

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

    

     

    
    

     
 if(!(S&(1<<j))&&i!=j&&d[i][j]!=-1)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 if(dp[S|(1<<j)][j]==-1)
     
    
   

    

     

    
    

     

       dp[S|(1<<j)][j]=dp[S][i]+d[i][j] ;
     
    
   

    

     

    
    

     
 else
     
    
   

    

     

    
    

     

       dp[S|(1<<j)][j]=min(dp[S|(1<<j)][j],dp[S][i]+d[i][j]) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 int ans = INF ;
     
    
   

    

     

    
    

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

    

     

    
    

     
 if(dp[(1<<num)-1][i]!=-1&&dg[i]!=-1)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 int x=a[i]/m,y=a[i]%m ;
     
    
   

    

     

    
    

     

       ans = min(ans,dp[(1<<num)-1][i]+dg[i]-g[x][y]) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 cout<<( ans!=INF ? ans : 0)<<endl ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int Tx,x,y ;
     
    
   

    

     

    
    

     
 scanf("%d",&Tx) ;
     
    
   

    

     

    
    

     
 while(Tx--)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 memset(dp,-1,sizeof(dp)) ;
     
    
   

    

     

    
    

     
 memset(d,-1,sizeof(d)) ; // 如果两点无法达到为 -1
     
    
   

    

     

    
    

     
 memset(dg,-1,sizeof(dg)) ; // 如果某点无法到达边界为 -1
     
    
   

    

     

    
    

     
 memset(flag,-1,sizeof(flag)) ; // 如果某点没有怪物为 -1
     
    
   

    

     

    
    

     
 scanf("%d%d",&n,&m) ;
     
    
   

    

     

    
    

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

    

     

    
    

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

    

     

    
    

     
 scanf("%d",&g[i][j]) ;
     
    
   

    

     

    
    

     
 bool fx=false ;
     
    
   

    

     

    
    

     
 scanf("%d",&num) ;
     
    
   

    

     

    
    

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

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 scanf("%d%d",&x,&y) ;
     
    
   

    

     

    
    

     

       a[i]=x*m+y ;
     
    
   

    

     

    
    

     
 if(g[x][y]==-1) fx=true ;
     
    
   

    

     

    
    

     

       flag[x][y]=i ;// 标记此点有怪物
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 if(fx)// 如果某个点无法到达
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 cout<<0<<endl ;
     
    
   

    

     

    
    

     
 continue ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 for(int i=0 ;i<num ;i++) // 求每个怪物的间距
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       x=a[i]/m  ; y =a[i]%m ;
     
    
   

    

     

    
    

     

       dg[i]=bfs(x,y)+g[x][y] ; // 距离最近的边界的距离
     
    
   

    

     

    
    

     
 int u = flag[x][y] ;
     
    
   

    

     

    
    

     

       d[u][u]=0 ;
     
    
   

    

     

    
    

     

       dp[1<<i][i]=dg[i] ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       DP_SC() ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return 0 ;
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: blog.csdn.net，作者：Linux猿，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/nyist_zxp/article/details/38046525