AC95. 费解的开关
题目描述
25盏灯排成一个5x5的方形。每一个灯都有一个开关，游戏者可以改变它的状态。每一步，游戏者可以改变某一个灯的状态。游戏者改变一个灯的状态会产生连锁反应：和这个灯上下左右相邻的灯也要相应地改变其状态。

我们用数字“1”表示一盏开着的灯，用数字“0”表示关着的灯。

总体思路为，答案的情况完全取决于第一行的情况，因此具体操作为（见“疑惑”）当第一行情况决定后，对每盏灭着的灯都进行点亮操作由下面的灯进行点亮（因为对当前灯的反转也会将周围的灯反转），枚举完n-1行，对最后一行进行判断灯是否全亮，因为对最后一行的操作会影响到上一行，所以枚举最后一行的时候上面的灯是全亮着的，如果最后一行存在灭着的灯则这种解不存在。

疑惑：一开始没想清楚为什么要用op枚举所有情况，实际上op代表的是对于第一行每个元素按与不按的两种操作，并非重新生成了一种情况。倘若op等于1（00001），则代表着对第1行（数组下标为0）的第2个元素进行反转操作g[0][1]。由于下一行是否反转取决于上一行，因此第一行的是否反转已经确定了结果（第一行的操作完全确定了答案）。而由于第一行有五个元素，每个元素都有按或不按两种情况，因此所有情况为2^5=32,也就是从00000(对第一行的台灯全部不进行反转操作)到11111（对第一行的情况全部操作）。对所有操作枚举一遍的结果取min即可得出最小值。
如果从第二行开始枚举，实际上情况只有一种，也就是第一行情况已经确定了，第二行的情况也就确定了，只有一个值。达不到最优的效果。

以下为代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;
const int N = 6;

char g[N][N], backup[N][N];
int dx[5] = {-1, 0, 1, 0, 0}, dy[5] = {0, 1, 0, -1, 0};

void turn(int x,int y)
{
    for(int i=0;i<5;i++)
    {
        int a=x+dx[i],b=y+dy[i];
        if(a<0 || b<0 || a>4 || b>4)//超出边界
            continue;
        g[a][b]^=1;//该操作为将字符'0'与'1'反转
    }
}
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        for(int i=0;i<5;i++)    cin>>g[i];

        int res=10;
        for(int op=0;op<32;op++)
        {
            memcpy(backup,g,sizeof g);//对g进行备份，下一轮需要用
            int step=0;
            for(int i=0;i<5;i++)
            {
                if(op>>i&1)//对第一行的操作
                {
                    step++;
                    turn(0,i);
                }
            }
            for(int i=0;i<4;i++)
            {
                for(int j=0;j<5;j++)
                {
                    if(g[i][j]=='0')
                    {
                        turn(i+1,j);
                        step++;
                    }
                }
            }
            bool dark=false;
            for(int i=0;i<5;i++)
            {
                if(g[4][i]=='0')
                {
                    dark = true;
                    break;
                }
            }
            if(!dark)   res=min(step,res);
            memcpy(g,backup,sizeof g);
        }
        if(res>6)   res=-1;
        cout<<res<<endl;
    }
    return 0;
}