第一讲递归与递推例题 AcWing 95. 费解的开关

Bertha 。 2023-09-26 21:49 2阅读 0赞

## 第一讲 递归与递推 例题 AcWing 95. 费解的开关 ##

### 原题链接 ###

[AcWing 95. 费解的开关][AcWing 95.]

### 算法标签 ###

递推 位运算

### 思路 ###

初始时，所有灯的状态（执行以该灯为中心的开关操作）未确定，所以第一行的开关是待定的，第一行的0既可以通过自身的开关改变，又可以通过第二行相应位置（下方）的灯来改变  
故对第一行的开关操作与否进行枚举，按二进制00000即表明全不操作，11111表明全进行操作  
第一行的操作确定后，第一行的01状态也就确定了，那么第一行的0就只能通过第二行的对应位置来进行改变  
第一行的0通过第二行的灯操作全变为1后，第一行的状态就确定了，那么第二行就无法通过自身的灯变换操作来使第二行的0变为1（不然会对第一行影响），只能通过第三行相对位置的灯操作来改变  
依次类推，直到第四行的01状态确认后，由于没有第六行来对第五行进行操作，第五行的状态也就确定了  
故最后对第五行进行判断，第五行全为1时说明此第一行的状态（例如01110）对后续的的全部更改有效

### 代码 ###

#include<bits/stdc++.h>
    #define int long long
    #define rep(i, a, b) for(int i=a;i<b;++i)
    #define Rep(i, a, b) for(int i=a;i>b;--i)
    #define x first
    #define y second
    #define ump unordered_map
    #define pq priority_queue
    #define pb push_back
    using namespace std;
    typedef pair<int, int> PII;
    const int N=6;
    char g[N][N], back[N][N];
    int dx[5]={-1, 0, 1, 0, 0}, dy[5]={0, 1, 0, -1, 0};
    inline int rd(){
       int s=0,w=1;
       char ch=getchar();
       while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
       while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
       return s*w;
    }
    void put(int x) {
        if(x<0) putchar('-'),x=-x;
        if(x>=10) put(x/10);
        putchar(x%10^48);
    }
    void turn(int x, int y){
        rep(i, 0, 5){
            int xx=x+dx[i], yy=y+dy[i];
            // if(xx>0&&xx<5&&yy>=0&&yy<5){
            //     g[xx][yy]^=1;
            // }
            if(xx<0||xx>=5||yy<0||yy>=5){
                continue;
            }
            g[xx][yy]^=1;
        }
    }
    signed main(){
        ios::sync_with_stdio(false);
        cin.tie(0);
        cout.tie(0);
        int t=rd();
        while(t--){
            rep(i, 0, 5){
                scanf("%s", g[i]);
            }   
            int res=7;
            rep(i, 0, 1<<5){
                memcpy(back, g, sizeof g);
                int cnt=0;
                rep(j, 0, 5){
                    if(i>>j&1){
                        cnt++;
                        turn(0, 4-j);
                    }
                }
                rep(j, 0, 4){
                    rep(k, 0, 5){
                        if(g[j][k]=='0'){
                            cnt++;
                            turn(j+1, k);
                        }
                    }
                }
                bool suc=false;
                rep(j, 0, 5){
                    if(g[4][j]=='0'){
                        suc=true;
                        break;
                    }
                }
                if(!suc){
                    res=min(res, cnt);
                }
                memcpy(g, back, sizeof g);
            }
            if(res>6){
                res=-1;
            }
            printf("%lld\n", res);
        }
        return 0;
    }

### 参考文献 ###

[AcWing 95. 费解的开关y总讲解][AcWing 95. _y]

![在这里插入图片描述][9cb4cb80a18345158f8a69e2f196e5b9.png]

[AcWing 95.]: https://www.acwing.com/problem/content/97/
[AcWing 95. _y]: https://www.acwing.com/video/114/
[9cb4cb80a18345158f8a69e2f196e5b9.png]: https://img-blog.csdnimg.cn/9cb4cb80a18345158f8a69e2f196e5b9.png