思路

发现输入的数组只有 $5\times 6$ 可以直接暴力搜索，但是因为 $2^{30}$ 的时间复杂度还是不可接受考虑优化。

考虑一个性质：如果第一行修改的灯泡确定那么方案是可以在 $O(5\times 6)$ 的时间复杂度内求解出来的。

因为在第一行修改结束之后，可以是第一行发生变化的灯泡就是有下面一行中与其紧挨着的那个灯泡。假设需要找到一个合法的方案，那么前一行的所有灯泡都需要被熄灭，所以这一行的操作也就确定了。于是我们就可以使用递推的方式求解出方案，再去判断最后一行是否合法。

时间复杂度是 $O(1)$ 的，这个常数应该在 $2^6\times 30$ 左右也就是大约 $2000$ 非常的优秀。

AC Code

#include<iostream>  
using namespace std;  
const int N=10;  
int a[N][N],b[N][N],dx[]={0,1,0,-1,0},dy[]={0,0,1,0,-1};  
bool ans[N][N];  
void change(int x,int y){  
    for(int i=0;i<=4;i++){  
        int xx=x+dx[i],yy=y+dy[i];  
        if (xx<1||xx>5||yy<1||yy>6) continue;  
        a[xx][yy]^=1;  
    }  
}  
bool ck(){  
    for(int i=1;i<=5;i++){  
        for(int j=1;j<=6;j++){  
            if(a[i][j]){  
                return 0;  
            }  
        }  
    }  
    return 1;  
}  
void solve(){  
    for(int i=1;i<=5;i++){  
        for(int j=1;j<=6;j++){  
            cin>>b[i][j];  
        }  
    }  
    for(int p=0;p<(1<<6);p++){  
        for(int i=1;i<=5;i++){  
            for(int j=1;j<=6;j++){  
                a[i][j]=b[i][j];  
                ans[i][j]=0;  
            }  
        }  
        for(int i=1;i<=6;i++){  
            if(p>>(i-1)&1){  
                change(1,i);  
                ans[1][i]=1;  
            }  
        }  
        for(int i=2;i<=5;i++){  
            for(int j=1;j<=6;j++){  
                if(a[i-1][j]){  
                    change(i,j);  
                    ans[i][j]=1;  
                }  
            }  
        }  
        if(ck()){  
            for(int i=1;i<=5;i++){  
                for(int j=1;j<6;j++){  
                    cout<<ans[i][j]<<' ';  
                }  
                cout<<ans[i][6]<<'\n';  
            }  
            return;  
        }  
    }  
}  
int main(){  
    ios::sync_with_stdio(false);  
    cin.tie(0);  
    int T;  
    cin>>T;  
    for(int i=1;i<=T;i++){  
        cout<<"PUZZLE #"<<i<<'\n';  
        solve();  
    }  
    return 0;  
}