关灯问题总结

题目描述

给定一个5*5只有0/1的矩阵，1表示灯开着，0表示灯关着，每个灯有唯一的一个开关，按动一个灯的开关时，他的相邻灯盏状态也会改变（上下左右）。问是否存在一个一种方案，使其在n步之内关掉或者打开所有的灯。

分析一

首先考虑暴力解法，肯定有一个dfs，递归枚举每个位置是否翻转，到达底界时应用当前方案并更新最值。复杂度O(2^25)(不用计算了，
33554432 )，这个复杂度是必定超时的。

分析二

依据题目给定的条件，一个开关按动时，他的周围灯的状态也会随之改变。观察第一行，能够改变第一行状态的只有第一行自身改变和第二行改变时的被动改变。假设当前我们要把所有灯打开（全为1），那么对于第一行的一个灯light[0][j]==‘0’，想要改变他的状态只有改变他自身和改变light[1][j]这两个位置。假设当前通过改变第一行和第二行的某些位置，使得第一行全为1，那么第一行就可以不用放在考虑范围之内了。接下来我们考虑第二行，能够改变第二行的操作只有改变第二行和第三行，因为第一行已经全是1，所以改变第二行会影响第一行，因此我们只能改变第三行来使第二行全为1。以此类推。。。
假设按照上面的操作我们已经将前4行的状态全部改变为1，对于最后一行，能够改变其状态的只有它的下一行，但是遗憾的是，它本身已经使最后一行了，所以它的0状态是没法被改变的。那么如何检查当前按照这种方案是否已经得到了全是1的状态呢。因为前4行已经全是1，因此只要检查最后一行是否全是1就可以知道按照这种方案得到的状态是否符合题意。
到这里，我们可以发现，对于第i行，我们总是改变第i+1行（不包括最后一行）使其全为1。也就是说，第二行改变依赖于第一行的状态，第三行的改变依赖于第二行的状态，···，第i+1行的改变依赖于第i行的状态，可以发现只要第一行的状态确定了，那么其他行如何改变也就确定了。所以，我们只要枚举第一行的灯如何按动，就唯一确定了其他行的按动方案。
因此，问题就转换成了枚举第一行的翻转方案，并且应用当前枚举到的方案，向下应用，对于最后一行检查其是否全为1即可。
总复杂度O(2^5*(5*5+20*5+5))。
这里我使用状态来进行枚举（状态压缩）。因为对于一个位置，要么按要么不按，（类似于背包问题的放不放），因此枚举数就是2^5（2*2*2*2*2），对应2进制就是00000-11111。

需要注意的是，对于一个灯的位置，只有奇数次操作才是有效的，偶数次等于没有操作，这一点也是分析二的前提。

相似问题还有POJ的3279.题目类似，可以使用相同解法

解决方案

#include<bits/stdc++.h>
using namespace std;
//#define LOCAL
#define Mod 998244353
#define ll long long int
#define mset(a,b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
const int maxn=2e3+5;
char mp[10][10];
int dx[5]={0,1,-1,0,0};
int dy[5]={0,0,0,-1,1};
void turn(int x,int y){
    for(int i=0;i<5;i++){
        int a=x+dx[i],b=y+dy[i];
        if(a>=0&&a<5&&b>=0&&b<5){
            mp[a][b]^=1;
        }
    }
}
int dowork(){
    int ans=INF;
    for(int i=0;i<1<<5;i++){
        int res=0;
        char backup[10][10];
        memcpy(backup,mp,sizeof(backup));
        for(int j=0;j<5;j++){
            if(i>>j&1){
                res++;
                turn(0,j);
            }
        }
        for(int i=0;i<4;i++){
            for(int j=0;j<5;j++){
                if(mp[i][j]=='0'){
                    res++;
                    turn(i+1,j);
                }
            }
        }
        bool suc=true;
        for(int j=0;j<5;j++){
            if(mp[4][j]=='0'){
                suc=!suc;
                break;
            }
        }
        ans=suc?min(ans,res):ans;
        memcpy(mp,backup,sizeof(mp));
    }
    if(ans>6) return -1;
    else return ans;

}
int main() {
#ifdef LOCAL
    freopen("in.in","r",stdin);
#endif // LOCAL
    int t;
    scanf("%d",&t);
    while(t--){
        for(int i=0;i<5;i++){
            scanf("%s",mp+i);
        }
        printf("%d\n",dowork());
    }
    return 0;
}

个人小结：之前对这个问题没有理解透彻，就下决心总结一番。