题目描述

每次点击矩阵里面的一个大，一个点为中心的十字形范围内地开关状态都会改变，问最少点击几次可以全部关闭，多种方案时，按照从上到下，从左到右的优先级选择

样例

无

blablabla

算法1

(不知道应该叫啥名) $O(2^16*16)$(大概？)

对于这题有性质：每个开关最多被点击一次

用一个16位二进制数的每一位的0或1代表对应的开关是否点击
枚举从0-2^16-1的每一个数，对矩阵进行操作，但注意，其实不用真的去操作，我们可以用一个数组x和y表示i行和i列分别操作了多少x[i]和y[i]次，来降低复杂度，这里还需要注意，这样记录的话，针对我们点击的这个点相当于反转了两次，但实际上只反转了一次，那么，只要对这个点再取一次反，针对这点就相当于一共取反了三次等价于取反了一次，与题意相符，最后再判断操作后的矩阵是否正确就可以了，代码有注释。

C++ 代码

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
bool ma[5][5];
void print(int ans){ 
    for(int i=0;i<16;++i){
        if((ans>>i)&1){
            cout<<i/4+1<<" "<<i%4+1<<endl;
        }
    }
}
int main(){
    string s;
    for(int i=1;i<=4;++i){//读入数组，开为1关为0 
        cin>>s;
        for(int j=1;j<=4;++j){
            if(s[j-1]=='-') ma[i][j]=1;
            else ma[i][j]=0;
        }
    }
    int minn=9999999;//最少开关次数 
    int ans;
    for(int i=0;i<=(1<<16)-1;++i){//枚举开关方案 

        bool mb[5][5];//临时用来储存的数组 
        for(int j=1;j<=4;++j) {
            for(int k=1;k<=4;++k){
                mb[j][k]=ma[j][k];
            }
        }
        int x[5]={},y[5]={};//x和y数组用来记录对应行和列取反了多少次 
        int temp=i;//复制一个i 
        int xx=1;
        int tot1=0;//记录开关次数 
        int yy=1;
        bool ok=1;


        while(temp){
            if(temp&1){
                tot1++;
                if(tot1>=minn) {
                    ok=0;
                    break;//剪支 
                }
                x[xx]++;
                y[yy]++;
                mb[xx][yy]=!mb[xx][yy];//把点击的点取反 
            }
            ++yy;
            if(yy>4) {
                yy=1;
                ++xx;
            }
            temp>>=1;
        }
        if(!ok) continue;



        for(int j=1;j<=4;++j){//判断是否合法 
            for(int k=1;k<=4;++k){
                int tot=x[j]+y[k];
                if(mb[j][k]==1&&((tot&1)==1)){
                    ok=0;
                    break;
                }
                if(mb[j][k]==0&&((tot&1)==0)){
                    ok=0;
                    break;
                }
            }
            if(!ok) break;
        }


        if(ok) {//储存答案 
            minn=tot1;
            ans=i;
        }
    }
    cout<<minn<<endl;
    print(ans);//输出答案 
    return 0;
}

算法2

(我也不知道叫啥) $O(2^16*16)$

上中写法是将矩阵的状态存在数组中，这种是把矩阵的状态用一个16位二进制来表示，更加突出了二进制思想。和上种写法一样的用0-2^16-1之间的数去枚举点击方案，然后进行检查即可，这里的话，如果我们用0表示开，检查就会方便很多，直接判断当前矩阵的对应二进制数是不是0就可以了。那么如何实现十字形的取反操作呢？我们可以预处理一个change数组，之后直接^change[i][j]就可以了。代码有注释。

C++ 代码

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
typedef pair<int,int> pii; 

int state=0;
int get(int x,int y){//快速获得对应点的编号即在二进数中的位次 
    return x*4+y-4-1;
}
int change[5][5];
vector <pii> v,temp;
int main(){
    string s;
    v.clear();
    temp.clear();
    for(int i=1;i<=4;++i){
        cin>>s;
        for(int j=1;j<=4;++j){
            if(s[j-1]=='+'){
                state+=1<<(get(i,j));//将状态存在state中用加法在对应二进制数中加一即可 
            }
        }
    }
    for(int i=1;i<=4;++i){
        for(int j=1;j<=4;++j){
            for(int k=1;k<=4;++k){
                change[i][j]+=1<<(get(i,k));//相同行上取反 
                change[i][j]+=1<<(get(k,j));//相同列上取反，注意change只是记录哪几位要取反，把这位加上1，在^change[i][j]实现取反   
            }
            change[i][j]-=1<<(get(i,j));//由于实际上这个点只取反了一次 ，所以要减去一个 
        }
    }
    for(int i=0;i<(1<<16);++i){
        int now=state;
        temp.clear();
        for(int j=1;j<=16;++j){
            if((i>>(j-1))&1){
                int x=(j-1)/4+1,y=((j-1)%4)+1;
                now ^= change[x][y];//取反 
                temp.push_back(make_pair(x,y));
            }
        }
        if(!now&&(v.empty()||v.size()>temp.size())) {//判断 
            v=temp;
        }
    }
    cout<<v.size()<<endl;
    for(int i=0;i<v.size();++i){
        cout<<v[i].first<<" "<<v[i].second<<endl;
    }
}