费解的开关

题目描述

你玩过“拉灯”游戏吗？25 盏灯排成一个 5x5 的方形。每一个灯都有一个开关，游戏者可以改变它的状态。每一步，游戏者可以改变某一个灯的状态。游戏者改变一个灯的状态会产生连锁反应：和这个灯上下左右相邻的灯也要相应地改变其状态。
我们用数字“1”表示一盏开着的灯，用数字“0”表示关着的灯。下面这种状态

在改变了最左上角的灯的状态后将变成：

再改变它正中间的灯后状态将变成：

给定一些游戏的初始状态，编写程序判断游戏者是否可能在 6 步以内使所有的灯都变亮。

输入描述

第一行有一个正整数 n，代表数据***有 n 个待解决的游戏初始状态。
以下若干行数据分为 n 组，每组数据有 5 行，每行 5 个字符。每组数据描述了一个游戏的初始状态。各组数据间用一个空行分隔。
对于 30%的数据，n≤5；
对于 100%的数据，n≤500。

输出描述

输出数据一共有 n 行，每行有一个小于等于 6 的整数，它表示对于输入数据中对应的游戏状态最少需要几步才能使所有灯变亮。
对于某一个游戏初始状态，若 6 步以内无法使所有灯变亮，请输出“-1”。

输入样例

输出样例

3
2
-1

说明

从 0 到 3 的 Hamilton 路径有两条，0-1-2-3 和 0-2-1-3。前者的长度为 2+2+1=5，后者的长度为 1+2+1=4

思路

了解题意不难发现

每个开关至多被按下一次。 // 按下两次没有意义
开关的按下顺序不影响最终结果。
在上一行已经确定的情况下，下一行的点击是确定的。 // 否则没法打开上一行未打开的开关

当点击完倒数第二行时，若最后一行全都为打开的状态，则这样的点击是正确的一组解，所有只需要枚举第一行的点击方法，即可根据上面的三条性质确定每一种方法是否是一组有效解，然后获取最少的点击次数。
对于第一行开关的点击，可用一个整数进行转态压缩，每一位代表一个开关的点击，即遍历 0 ~ (1<<5)-1可枚举所有的点击方法。

示例代码

#include <iostream>
#include <string.h>

const int INF = 0x3F3F3F3F;
const int PRESSNUM = 6;
const int N = 5;
char board[N][N + 1];
char temp[N][N + 1];
int pressNum;

bool inBoard(int i, int j)
{
    return i >= 0 && j >= 0 && i < N && j < N;
}

const int _I[] = {-1, 0, 0, 1, 0};
const int _J[] = {0, -1, 0, 0, 1};

void press(int i, int j)
{
    pressNum++;
    for (int k = 0; k < 5; k++)
    {
        int ii = i + _I[k];
        int jj = j + _J[k];
        if (inBoard(ii, jj))
            temp[ii][jj] = temp[ii][jj] == '0' ? '1' : '0';
    }
}

int solve()
{
    int minp = INF;
    for (int s = 0; s < (1 << N); s++)
    {
        pressNum = 0;
        memcpy(temp, board, sizeof(board));
        for (int i = 0; i < N; i++)
            if (s & (1 << i))
                press(0, i);

        for (int i = 0; i < N - 1; i++)
        {
            for (int j = 0; j < N; j++)
            {
                if (temp[i][j] == '0')
                {
                    press(i + 1, j);
                    if (pressNum > PRESSNUM)
                        goto end_for;
                }
            }
        }
        { // goto不能跳过变量定义
            bool flg = true;
            for (int i = 0; i < N; i++)
                flg = flg && temp[N - 1][i] == '1';
            if (flg && pressNum < minp)
                minp = pressNum;
        }
    end_for:;
    }
    return minp == INF ? -1 : minp;
}

using namespace std;

int main(int argc, char const *argv[])
{
    int n;
    cin >> n;
    for (int k = 0; k < n; k++)
    {
        for (int i = 0; i < N; i++)
        {
            cin >> board[i];
        }
        cout << solve() << endl;
    }

    return 0;
}