一个n*m的房间有的房间是可破坏的，其他不可破坏，现在给你一些L型的灯，其中只有一个可以旋转，其他不能，让你用最少的灯覆盖所有的可破坏区域，且不能覆盖不可破坏的区域。

枚举旋转的灯，对剩下的DFS即可，状压存储已经被点亮的灯

#include "stdio.h"
#include "string.h"struct P
{int x,y;
}p[21];int ans,n,m,cnt,aim,b[21];
char str[210][210];int judge(int x,int y)
{if (x>=0 && x<n && y>=0 && y<m && str[x][y]=='#') return 0;return 1;
}void dfs(int k,int sum,int mark,int light)
{int i,j,ll;if (sum>=ans) return ;if (light==aim) {ans=sum; return ;}if (k>=cnt) return ;dfs(k+1,sum,mark,light);for (i=k;k<cnt;k++)if (i!=mark){ll=light|b[i];if (judge(p[i].x-1,p[i].y)==0 || judge(p[i].x,p[i].y+1)==0) continue;for (j=0;j<cnt;j++){if (p[i].x-1==p[j].x && p[i].y==p[j].y) ll|=b[j];if (p[i].x==p[j].x && p[i].y+1==p[j].y) ll|=b[j];}dfs(k+1,sum+1,mark,ll);}
}
int main()
{int i,j,mark,light;b[0]=1;for (i=1;i<=16;i++)b[i]=b[i-1]*2;while (scanf("%d%d",&n,&m)!=EOF){if (n+m==0) break;for (i=0;i<n;i++)scanf("%s",str[i]);cnt=0;for (i=0;i<n;i++)for (j=0;j<m;j++)if (str[i][j]=='.'){p[cnt].x=i;p[cnt].y=j;cnt++;}if (cnt==0){printf("0\n");continue;}ans=100000;aim=b[cnt]-1;dfs(0,0,-1,0);for (i=0;i<cnt;i++){if (judge(p[i].x-1,p[i].y) && judge(p[i].x,p[i].y-1)){mark=i;light=b[i];for (j=0;j<cnt;j++){if (p[j].x==p[i].x && p[j].y==p[i].y-1) light|=b[j];if (p[j].x==p[i].x-1 && p[j].y==p[i].y) light|=b[j];}dfs(0,1,mark,light);}if (judge(p[i].x,p[i].y-1) && judge(p[i].x+1,p[i].y)){mark=i;light=b[i];for (j=0;j<cnt;j++){if(p[j].x==p[i].x && p[j].y==p[i].y-1) light|=b[j];if(p[j].x==p[i].x+1 && p[j].y==p[i].y) light|=b[j];}dfs(0,1,mark,light);}if (judge(p[i].x,p[i].y+1) && judge(p[i].x+1,p[i].y)){mark=i;light=b[i];for (j=0;j<cnt;j++){if (p[j].x==p[i].x && p[j].y==p[i].y+1) light|=b[j];if (p[j].x==p[i].x+1 && p[j].y==p[i].y) light|=b[j];}dfs(0,1,mark,light);}}if (ans==100000) printf("-1\n");else printf("%d\n",ans);}return 0;
}