本文共 1967 字，大约阅读时间需要 6 分钟。
思路：
这个题完全就是暴力的，就是代码长了一点。
用到了状压，因为之前不知道状压是个东西，大佬们天天说，可是我又没学过，所以对状压有一点阴影，不过这题中的状压还是蛮简单的。
枚举所有情况，取开灯数最少的。
解释都在注释之中了。
#include #include #include #include #include #include #include #include #include #define fuck(x) cout<<#x<<" = "< < 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 >=1; } int y; int error=0,e;//error表示有几盏灯在没有旋转的情况下，照亮了不可照亮区域 for(int i=0;i 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 =ans){ continue;} if(light(i))ans=min(ans,num); } if(ans==inf){ans=-1;} printf("%d\n",ans); } return 0;}
转载于:https://www.cnblogs.com/ZGQblogs/p/9762130.html
