拉灯问题题解

#include <bits/stdc++.h>
using namespace std;
const int dx[5] = {0, 0, 0, 1, -1}; // 五个方向：自身+上下左右
const int dy[5] = {0, 1, -1, 0, 0};
int a[6][6], b[6][6];

void click(int x, int y) {
    for(int t = 0; t < 5; t++) {
        int nx = x + dx[t];
        int ny = y + dy[t];
        if(nx < 1 || nx > 5 || ny < 1 || ny > 5) continue;
        a[nx][ny] ^= 1;
    }
}

int main() {
    int n; scanf("%d", &n);
    while(n--) {
        for(int i = 1; i <= 5; i++)
            for(int j = 1; j <= 5; j++) 
                scanf("%1d", &a[i][j]), b[i][j] = a[i][j];
    
        int ans = 7;
        for(int x = 0; x <= 31; x++) { // x为5位二进制，表示第一行操作状态
            int tot = 0;
            // 枚举第一行所有可能操作
            for(int j = 1; j <= 5; j++) 
                if((x >> (j - 1)) & 1) {
                    ++tot;
                    click(1, j);
                }
            // 处理后续行，若当前灯不亮则点击下一行对应位置
            for(int i = 1; i <= 4; i++) 
                for(int j = 1; j <= 5; j++)
                    if(!a[i][j]) {
                        ++tot;
                        click(i + 1, j);
                    }
            // 检查是否所有灯都亮
            bool bk = true;
            for(int i = 1; i <= 5; i++) 
                for(int j = 1; j <= 5; j++) 
                    if(!a[i][j]) {
                        bk = false;
                        break;
                    }
            memcpy(a, b, sizeof(b)); // 恢复初始状态
            if(!bk) continue;
            ans = min(ans, tot);
            if(!ans) break;
        }
        printf("%d\n", ans == 7 ? -1 : ans);
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int dx[5]={0,0,0,1,-1}; //五个方向：自己+上下左右 
const int dy[5]={0,1,-1,0,0};
int a[6][6],b[6][6];
 
void click(int x,int y)
{
    for(int t=0;t<5;t++)
    {
        int nx=x+dx[t];
        int ny=y+dy[t];
        if( nx<1 || nx>5 || ny<1 || ny>5 ) continue;
        a[nx][ny]^=1;
    }
}
int main()
{
    int n;scanf("%d",&n);
    while(n--)
    {
        for(int i=1;i<=5;i++)for(int j=1;j<=5;j++) scanf("%1d",&a[i][j]),b[i][j]=a[i][j];
    
        int ans=7;
        for(int x=0;x<=31;x++)//x为5位二进制，表示第一行的操作状态：二进制后为1表示拉一下对应位置开关 
        {
            int tot=0;
            for(int j=1;j<=5;j++) if( (x>>(j-1))&1 ) ++tot,click(1,j);
            for(int i=1;i<=4;i++) 
                for(int j=1;j<=5;j++)
                    if( !a[i][j] )//第i行的需求由第i+1行操作解决，秒 
                    {
                        ++tot,click(i+1,j);
                    }
            bool bk=True;
            for(int i=1;i<=5;i++) for(int j=1;j<=5;j++) if(!a[i][j]){bk=False;break;}
            memcpy(a,b,sizeof(b));
            if(!bk)continue;
            ans=min(ans,tot);if(!ans)break;
        }
        if(ans==7) printf("-1\n");else printf("%d\n",ans);
    }
     
    return 0;
}