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