Home AcWing 95 费解的开关
Post
Cancel

AcWing 95 费解的开关

Link

一行有 5 个开关, 对应 32 种按法. 由此联想到用二进制的思想对这 32 种按法进行枚举.

对于每种按法, 首先应用于第一行. 这一点很好理解, 因为无论我们怎么按、从哪里开始, 如果只看第一行的变化, 都可以归结为这 32 种按法中的一种. 而按法并没有顺序要求, 因为是可逆的, 可以还原. 所以任何一种按法都等价于: 先按第一行, 然后再对剩下的行进行调整.

接下来我们调整的方法是, 尽可能地保证当前行的上一行变成全 1. 这是因为, 如果位于 (i,j) 处的元素是 0, 那么想要让它变为 1 并且不改变与它同行的其他元素, 就只能通过翻转它的上面或下面的元素来实现. 但是为了便于编码我们是按照从上到下的顺序进行调整的, 因此: 如果 (i,j) 处的元素是 0, 那么就翻转 (i+1,j) 处的元素.

按照这种做法, 我们能够保证第 0 到 3 行全都变成了 11111, 因此就只需要判断第 4 行中有没有 0. 如果有, 就说明这种按法不行, 否则就更新 ans.

最后就是判断 ans 有没有超过 6, 超过了就按 -1 输出.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <bits/stdc++.h>
using namespace std;
int n,ans;
char g[10][10],backup[10][10];
int dx[5]={0,-1,0,1,0},dy[5]={-1,0,1,0,0};
void Rev(int x,int y){
    for(int i=0;i<5;++i){
        int tx=x+dx[i],ty=y+dy[i];
        if(tx>=0&&tx<5&&ty>=0&&ty<5)
            g[tx][ty]^=1;
    }
}
int main() {
    scanf("%d",&n);
    while(n--){
        ans=10;
        for(int i=0;i<5;++i)
            scanf("%s",g[i]);
        memcpy(backup,g,sizeof(g));
        for(int k=0;k<32;++k){
            int cnt=0;
            for(int j=0;j<5;++j)
                if((k>>j)&1){
                    cnt++;
                    Rev(0,j);
                }
            for(int i=1;i<=4;++i)
                for(int j=0;j<5;++j)
                    if(g[i-1][j]=='0'){
                        cnt++;
                        Rev(i,j);
                    }
            bool flag=true;
            for(int j=0;j<5;++j)
                if(g[4][j]=='0'){
                    flag=false;
                    break;
                }
            if(flag) ans=min(ans,cnt);
            memcpy(g,backup,sizeof(g));
        }
        if(ans>6) ans=-1;
        printf("%d\n",ans);
    }
    return 0;
}
This post is licensed under CC BY 4.0 by the author.