思路：
这个题完全就是暴力的，就是代码长了一点。
用到了状压，因为之前不知道状压是个东西，大佬们天天说，可是我又没学过，所以对状压有一点阴影，不过这题中的状压还是蛮简单的。
枚举所有情况，取开灯数最少的。
解释都在注释之中了。
#include<iostream> #include<algorithm> #include<vector> #include<stack> #include<queue> #include<map> #include<set> #include<cstdio> #include<cstring> #define fuck(x) cout<<#x<<" = "<<x<<endl; #define ls (t<<1) #define rs ((t<<1)+1) using namespace std; typedef long long ll; typedef unsigned long long ull; const int maxn = 208; const int inf = 2.1e9; const ll Inf = 999999999999999999; const int mod = 1e9+7; const double eps = 1e-6; char mp[maxn][maxn]; int vis[maxn][maxn]; struct node { int x; int y; }; vector<node>u; int get_num(int x) { int ans = 0; while(x){ if(x&1){ans++;} x>>=1; } return ans; } int n,m; int turn1(int t,int ans) { int x=u[t].x,y=u[t].y; if(mp[x-1][y]=='.'&&vis[x-1][y]==1){ans++;} if(mp[x+1][y]=='.'&&vis[x+1][y]==0){ans--;} if(mp[x][y+1]=='#'){return 1;} if(mp[x+1][y]=='#'){return 1;} return ans; } int turn2(int t,int ans) { int x=u[t].x,y=u[t].y; if(mp[x-1][y]=='.'&&vis[x-1][y]==1){ans++;} if(mp[x][y+1]=='.'&&vis[x][y+1]==1){ans++;} if(mp[x+1][y]=='.'&&vis[x+1][y]==0){ans--;} if(mp[x+1][y]=='#'){return 1;} if(mp[x][y-1]=='.'&&vis[x][y-1]==0){ans--;} if(mp[x][y-1]=='#'){return 1;} return ans; } int turn3(int t,int ans) { int x=u[t].x,y=u[t].y; if(mp[x][y+1]=='.'&&vis[x][y+1]==1){ans++;} if(mp[x][y-1]=='.'&&vis[x][y-1]==0){ans--;} if(mp[x-1][y]=='#'){return 1;} if(mp[x][y-1]=='#'){return 1;} return ans; } //判断状态是否可行 bool light(int x) { memset(vis,0,sizeof(vis)); int k=u.size(); int kk[50];//kk记录有几盏灯是亮的 for(int i=0;i<k;i++){ if(x&1){kk[i]=1;} else{kk[i]=0;} x>>=1; } int y; int error=0,e;//error表示有几盏灯在没有旋转的情况下，照亮了不可照亮区域 for(int i=0;i<k;i++){ if(kk[i]){ x=u[i].x;y=u[i].y; if(mp[x-1][y]=='#'||mp[x][y+1]=='#'){error++;e=i;} //vis记录某房间被照亮的次数 vis[x-1][y]++;vis[x][y+1]++; vis[x][y]++; } } if(error>1){return false;} int num=0;//num记录有几个区域，应该被照亮而没有被照亮。 for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(mp[i][j]=='.'&&!vis[i][j]){num++;} if(mp[i][j]=='#'&&vis[i][j]>1){return false;} } } if(num>2){return false;} //tt是num的中间结果 int tt; if(error){ //turn 表示旋转，返回值其实是旋转之后满不满足题意 tt=turn1(e,num);if(tt==0){return true;} tt=turn2(e,num);if(tt==0){return true;} tt=turn3(e,num);if(tt==0){return true;} return false; } if(num==0){return true;} for(int i=0;i<k;i++){ if(kk[i]){ tt=turn1(i,num);if(tt==0){return true;} tt=turn2(i,num);if(tt==0){return true;} tt=turn3(i,num);if(tt==0){return true;} } } return false; } int main() { while(scanf("%d%d",&n,&m)!=EOF&&(n!=0&&m!=0)){ memset(mp,0,sizeof(mp)); for(int i=1;i<=n;i++){ scanf("%s",mp[i]+1); } memset(vis,0,sizeof(vis)); u.clear(); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(mp[i][j]=='.'){ u.push_back(node{i,j}); } } } int siz = u.size(); int k=(1<<siz); int num; int ans = inf; for(int i=0;i<k;i++){ num=get_num(i); if(num>=ans){continue;} if(light(i))ans=min(ans,num); } if(ans==inf){ans=-1;} printf("%d ",ans); } return 0; }