Vijos1197 费解的开关

题意

给出一个 $5\times 5$ 的 $0/1$ 矩阵，每次点击某一个点会改变自身及上下左右的状态。求把矩阵全部变为 $1$ 的最少步数。

多组数据，组数 $N\le 500$ 。

题解

考虑逐行递推，如果上一行 $(i,j)$ 是 $0$ ，那么就需要点击当前行的 $(i+1,j)$ 。最后校验最后一行是否全为 $1$ 即可。

但第 $1$ 行没有上一行，所以我们需要枚举第 $0$ 行的状态，答案即为所有状态的最小值。

#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

int t,s[7];
const int N=32;

inline void click(int x,int y);
inline int work(int first);

signed main()
{
    t=read();
    while (t--)
    {
        memset(s,0,sizeof(s));
        for (int i=1;i<=5;i++)
        {
            char ch[7]; scanf("%s",ch+1);
            for (int j=1;j<=5;j++) s[i]|=(ch[j]-'0')<<(j-1);
        }
        int ans=1e9;
        for (int i=0;i<N;i++) ans=min(ans,work(i));
        printf(ans>6 ? "-1\n" : "%d\n",ans);
    }
    return 0;
}

inline int work(int first)
{
    int ans=0,last[7];
    memcpy(last,s,sizeof(s));
    for (int i=1;i<=5;i++)
    {
        if (first>>(i-1)&1) continue;
        ans++;
        click(1,i);
    }
    for (int i=1;i<5;i++)
    {
        for (int j=1;j<=5;j++) //枚举上一行
        {
            if (s[i]>>(j-1)&1) continue;
            ans++;
            click(i+1,j);
        }
    }
    if (s[5]==N-1) return memcpy(s,last,sizeof(last)),ans;
    return memcpy(s,last,sizeof(last)),1e9;
}

inline void click(int x,int y) //点击后改变上下左右
{
    s[x]^=1<<(y-1);
    if (y>1) s[x]^=1<<(y-2);
    if (y<5) s[x]^=1<<y;
    if (x>1) s[x-1]^=1<<(y-1);
    if (x<5) s[x+1]^=1<<(y-1);
}