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