icpc live archive6454(状压搜索) - c++编程基础

https://icpcarchive.ecs.baylor.edu/external/64/6454.pdf

求最少的灯照亮所有.的区域，但不能照到#号区域，可以照到界限之外，每个.号上只能放一盏灯。灯照的区域为L形，灯在拐角处。大多数灯是这样没错，但有一盏灯比较特殊，可以是L的其他三种旋转体。

状态压缩搜索，状态为放置的灯的状态，（.）点最多只有15个，做好序号可以直接存进一个int型里。

代码（中间有一些比较繁琐）：

#include
  
   
#include
   
     #include
    
      #include
      #include
      
        #include
       
         #include
        
          #include
         
           #define LL long long #define MOD 100000007 #define INF 0x3f3f3f3f using namespace std; const int maxn=202; char g[maxn][maxn]; int opp[maxn][maxn]; bool done[100000]; int n,m,k,cnt,sx,sy,point; int dx[]={0,0,-1,1}; int dy[]={-1,1,0,0}; int aimx[20],aimy[20]; struct node { int w,key,stat,no;//w为走的步数，key为可以放灯的点状态，stat为灯照亮的区域（一定是15个点中的嘛），no为还有几个特殊灯没放。 node(int ww=0,int k=0,int st=0,int n=0) { w=ww;key=k;stat=st;no=n; } }; bool is_ill(int x,int y) { return x<0||x>=n||y<0||y>=m; } int bfs() { queue
          
           q; memset(done,0,sizeof done); q.push(node(0,k,k,1)); done[k]=1; while(!q.empty()) { node e=q.front();q.pop(); for(int i=0;i