11.18 第4关 O((2^n)*n^2)题解

· · 个人记录

题目传送门

考虑到问题有一个重要特点：操作与顺序无关：如先摁(0,0)再摁(2,2)与先摁(2,2)再摁(0,0)等价。故排列问题简化为组合问题。最naive的想法就是枚举所有2^{25}种情况，但显然有很多多余情况无需枚举。

既然已经是组合问题，那么一个很好的性质就是摁灯的顺序（即排列）可任意，不妨考虑从第一排开始摁。

更进一步地，可以发现第一排的摁法一旦确定，第二排的摁法同样也确定了，因为第一排摁完之后还没亮的只能通过摁第二排来摁（这里也是很好地利用了边界的性质）。那么以此类推，3，4，5排的摁法都确定了，最后只要验证一下第5排是否全亮就行了。如果全亮，更新答案即可。

总之，以上方法的本质就是在等价转化问题后进行剪枝。

另外，在枚举第一排摁法时，为了避免多层循环，代码运用了状态压缩的小trick，它将一种摁法跟一个二进制数进行了一一映射（如：10010代表摁了第1和第4个灯）。（感觉有些类似机器学习做分类问题时用的one-hot预处理）

对了，总时间复杂度O(2^nn^2)。

#include<bits/stdc++.h>
using namespace std;
int c[7][7],ori[7][7],cnt;//cnt是步骤数计数器

void swch(int i,int j){//一次摁灯操作；^是异或操作，1^1=0，0^1=1
    c[i-1][j]^=1;
    c[i+1][j]^=1;
    c[i][j-1]^=1;
    c[i][j+1]^=1;
    c[i][j]^=1;
}

void ini(){//初始化，每次在c数组上操作
    cnt=0;
    for(int i=1;i<=5;i++){
        for(int j=1;j<=5;j++){
            c[i][j]=ori[i][j];
        }
    }
}

int main(){
    for(int i=1;i<=5;i++){
        for(int j=1;j<=5;j++){
            ori[i][j]=getchar()-'0';//getchar就是读入一个字符
        }
        getchar();//吞掉换行符
    }
    int mn=INT_MAX;
    for(int i=0;i<(1<<5);i++){//状态压缩，解释见上文，(1<<i)的含义是2的i次方（将二进制1左移i位）
        ini();
        for(int j=0;j<5;j++){
            if((1<<j)&i){//&是二进制按位与，这里的含义就是摁法i的第j位有1就会返回1，否则返回0
                cnt++;
                swch(1,j+1);
            }
        }
        for(int j=2;j<=5;j++){
            for(int k=1;k<=5;k++){
                if(!c[j-1][k]){//如果上一行的灯没亮，摁它下面这个灯
                    swch(j,k);
                    cnt++;
                }
            }
        }
        //下面在验证最后一行是否全是1
        bool flag=1;
        for(int j=1;j<=5;j++){
            if(!c[5][j]){
                flag=0;
                break;
            }
        }
        if(flag) mn=min(mn,cnt);
    }
    if(mn==INT_MAX) puts("-1");
    else cout<<mn;

    return 0;
}