【题解】TYVJ | JoyOI P1266 【费解的开关】

这里固定了第一行,后面的可行解也就唯一确定了,

所以只需枚举第一行的点击方式,就可以推出2,3,4行的方式,最后看第5行是否为全0,判断输出即可

 

代码这里使用了@Secret缄墨的,我不想去实现这个程序(太菜了)

#include <bits/stdc++.h>

inline void read(int &x)
{
    x = 0;char ch = getchar();
    char c = ch;
    while(ch > '9' || ch < '0')c = ch, ch = getchar();
    while(ch <= '9' && ch >= '0')x = x * 10 + ch - '0', ch = getchar();
    if(c == '-')x = -x;
}
inline int min(int a, int b){return a > b ? b : a;}

const int INF = 0x3f3f3f3f; 
const int MAXN = 50 + 10;

int g[MAXN][MAXN],n,ans,tmp[MAXN][MAXN];

void change(int x, int y)
{
    tmp[x][y] ^= 1;
    if(x - 1)
        tmp[x - 1][y] ^= 1;
    if(y - 1)
        tmp[x][y - 1] ^= 1;
    if(y + 1 <= n)
        tmp[x][y + 1] ^= 1;
    if(x + 1 <= n)
        tmp[x + 1][y] ^= 1;
}

int t;
char s[MAXN];

int main()
{
    read(t);
    n = 5;
    for(;t;--t)
    {
        memset(g, 0, sizeof(g));
        memset(tmp, 0, sizeof(tmp));
        ans = INF;
        for(int i = 1;i <= n;++ i)
        {
            scanf("%s", s + 1);
            for(int j = 1;j <= n;++ j)
                g[i][j] = (s[j] - '0') ^ 1;
        }
        for(register int s = 0;s < (1 << n);++ s)
        {
            for(int i = 1;i <= n;++ i)
                for(int j = 1;j <= n;++ j)
                    tmp[i][j] = g[i][j];
            bool ok = true;
            register int tmp = s;
            register int k = 1;
            int cnt = 0;
            while(tmp)
            {
                if(tmp & 1)
                    change(1, k),++ cnt;
                ++ k;tmp >>= 1;
            }
            for(register int j = 2;j <= n;++ j)
                for(k = 1;k <= n;++ k)
                    if(::tmp[j - 1][k])
                        change(j, k), ++ cnt;
            for(register int j = 1;j <= n;++ j)
                if(::tmp[n][j])
                    ok = false;
            if(ok)
                ans = min(ans, cnt);
        }
        if(ans > 6)
            printf("-1\n");
        else printf("%d\n", ans);
    }
    return 0;
}