HDU 4770 Lights Against Dudely -- 2013 杭州赛区现场赛-A（状态压缩）

题目链接~~>

做题感悟：以前在杭州赛区重现赛时做过这题，当时只知道暴力，而且没有看到有一盏特殊灯，结果以两题结束。

解题思路：因为只有 15 盏灯，可以用状态压缩，枚举每一种情况（在其中还要枚举特殊灯），参考了一下某大牛的代码才AC。

代码：

      #include<stdio.h>
      #include<queue>
      #include<string.h>
      #include<stdlib.h>
      #include<string.h>
      #include<algorithm>
      #include<iostream>
      #define INT long long int
      const int INF = 99999999 ;
      using namespace std ;
      const int MX = 200 + 10 ;
      typedef pair<int,int> PI;
      vector<PI>v ;
      bool IS[MX] ;
      int n,m,M ;
      char s[MX][MX] ;
      int vis[MX],d[MX][MX] ;
      int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1} ; // 上 右 下 左 0 1 2 3
      bool judge()
      {
      for(int i=0 ;i<M ;i++)
      if(!vis[i])  return false ;
      return true ;
      }
      void put(int x,int y,int px,int py)// 安放一般灯
      {
      int sx,sy,tx,cnt=d[x][y] ;
      int dn[2]={px,py} ;
      bool flag=false ; // 用来判断是否可以放
      for(int i=0 ;i<2 ;i++) // 判断是否可以放
       {
       tx=dn[i] ;
       sx=x+dx[tx] ;
       sy=y+dy[tx] ;
      if(sx<0||sy<0||sx>=n||sy>=m)  continue ;
      if(s[sx][sy]=='#')
       {
       flag=true ;
      break ;
       }
       }
      if(!flag) // 可以放
       {
       vis[cnt]++ ;
       IS[cnt]=true ;
      for(int i=0 ;i<2 ;i++)
       {
       tx=dn[i] ;
       sx=x+dx[tx] ;
       sy=y+dy[tx] ;
      if(sx<0||sy<0||sx>=n||sy>=m)  continue ;
       vis[d[sx][sy]]++ ;
       }
       }
      }
      void clear(int x,int y,int px,int py) // 清除
      {
      int sx,sy,tx,dn[2]={px,py} ;
       IS[d[x][y]]=false ;
       vis[d[x][y]]-- ;
      for(int i=0 ;i<2 ;i++)
       {
       tx=dn[i] ;
       sx=x+dx[tx] ;
       sy=y+dy[tx] ;
      if(sx<0||sy<0||sx>=n||sy>=m)  continue ;
       vis[d[sx][sy]]-- ;
       }
      }
      void work(int x,int y,int px,int py,int nx,int ny) // 安放特殊灯
      {
      int cnt = d[x][y] ;
      if(IS[cnt])  // 说明安放过
       clear(x,y,px,py) ;// 清除以前安放的灯以及灯光
       put(x,y,nx,ny) ; // 安放
      }
      int main()
      {
      while(scanf("%d%d",&n,&m),(n||m))
       {
       M=0 ;
       v.clear() ;
      memset(d,0,sizeof(d)) ;
      for(int i=0 ;i<n ;i++)
       {
      scanf("%s",s[i]) ;
      for(int j=0 ;j<m ;j++)
      if(s[i][j]=='.')
       {
       d[i][j]=M++ ;
       v.push_back(make_pair(i,j)) ;
       }
       }
      if(!M)
       {
      cout<<0<<endl ;
      continue ;
       }
      int ans=INF ;
      for(int i=0 ;i<(1<<M) ;i++) // 枚举各种状态
       {
      int num=0 ;
      memset(vis,0,sizeof(vis)) ;
      memset(IS,false,sizeof(IS)) ;
      for(int j=0 ;j<M ;j++)
      if((1<<j)&i)
       {
       num++ ; // 记录灯的个数
       put(v[j].first,v[j].second,0,1) ; // 放普通灯
       }
      if(num>=ans)  continue ;
      if(judge())  ans = min(ans,num) ;
      else  // 安放特殊灯
       {
      for(int j=0 ;j<M ;j++) // 尝试每个灯
      if((1<<j)&i)
       {
       work(v[j].first,v[j].second,0,1,1,2) ; //清除上 右 / 安放 右 下
      if(judge()) { ans = min(ans,num) ; break ; }
       work(v[j].first,v[j].second,1,2,2,3) ; //清除 右 下 / 安放 左 下
      if(judge()) { ans = min(ans,num) ; break ; }
       work(v[j].first,v[j].second,2,3,0,3) ; //清除 左 下 / 安放 上 左
      if(judge()) { ans = min(ans,num) ; break ; }
       work(v[j].first,v[j].second,0,3,0,1) ; //清除 上 左 / 安放 上 右
       }
       }
       }
      printf("%d\n",ans==INF ? -1 : ans) ;
       }
      return 0 ;
      }
  
 

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

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