费解的开关（位运算+递推）

题目描述：

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

我们用数字“1”表示一盏开着的灯，用数字“0”表示关着的灯。下面这种状态

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

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

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

输入格式

第一行输入正整数nn，代表数据中共有nn个待解决的游戏初始状态。

以下若干行数据分为nn组，每组数据有5行，每行5个字符。每组数据描述了一个游戏的初始状态。各组数据间用一个空行分隔。

输出格式

一共输出nn行数据，每行有一个小于等于6的整数，它表示对于输入数据中对应的游戏状态最少需要几步才能使所有灯变亮。

对于某一个游戏初始状态，若6步以内无法使所有灯变亮，则输出“-1”。

数据范围

0<n≤5000

输入样例：

输出样例：

3
2
-1

这道题很多人都有搜索做，搜索也可以做，不过复杂度应该是3*10^8左右，如果用递推复杂度只有2^5*4*5*5000,1600000,。

费解的开关（位运算+递推）_初始状态

上面是递推，下面是搜索，可以看到，复杂度降低了很多，这里来写一下递推做法。

首先我们要枚举第一行灯开关的所有情况，那么如果要改变第一行的灯的状态，那么就只能更改第二行的位于该灯下面的那个开关来改变。

费解的开关（位运算+递推）_递推_02

如果我们固定了第一行，那么为了将全部都变成绿色，就必须利用第二行。例如，(1,1)(1,1)是红色，为了让它变成绿色，就必须更改(2,1)(2,1)。为了让(1,4)(1,4)变成绿色，就必须更改(2,4)(2,4)。
更改后图形如下:

费解的开关（位运算+递推）_#include_03

那么我们再固定第二行，利用第三行来更改它（就像用第一行来更改第二行一样），就变成了

费解的开关（位运算+递推）_#include_04

同理，更改第三行

费解的开关（位运算+递推）_初始状态_05

再更改第四行

费解的开关（位运算+递推）_递推_06

这是我们发现，最后还有一个灯是关着的，所以，这说明第一行的灯如果是这样的情况就无法成立
那么就继续枚举第一行的点击方式，再继续按照刚才的方法，判断能否点完即可。

这道题目首先看一眼，我们就可以知道必然与位运算有着密切的关系，因为出现了0和1，这是一个重要的发现，接着我们在仔细分析题意，我们知道如果纯暴力枚举的话，必然是会超时的，那么如何优化呢？因此我们需要从题目中找出非常有用的性质来优化，这是一个大致的思路方向

每一个位置顶多只会操作一次。因为如果操作两次的话，相当于不操作，必然是不满足最优解。

在一套方案中，操作的顺序无关紧要，这一个略加思索便可得知

最重要的性质，如果我们确定了第I行的操作方案的话，那么后面的行数都可以依此递推，下面给出一个详细的解答。

11011
10110
01111
11111
比如说这个例子，如果我们确定了第1行，那么第二行所有的0(坐标：a[i][j])
都只能是第三行a[i+1][j]来修改了，因为如果你第二行修改的话，那么第一行将会打乱，下面每一行依此类推。

我一开始是不理解为什么要枚举32种第一行的所有情况，可能很多人和我一样不理解。

如果不枚举，就让第一行不动，那么最后会发现需要的次数>6次了，那么有没有可能让次数<=6呢？
有的，就是稍微改一下第一行的状态，那怎么改呢，没人知道，只能一个一个按钮去试，那不正好是枚举32次吗。所以不枚举直接递推的话输出的所有结果都是-1，枚举只是为了找到最小的答案。

AC代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<stdlib.h>
#include<ctime>
#include<map>
const int INF = 0x3f3f3f3f;
using namespace std;
int i,j,k,l;
int n,m;
int ans;
char a[10][10],cpy[10][10];
int dx[6]={0,-1,0,1,0},dy[6]={0,0,1,0,-1};
void turn(int x,int y)
{
    for(l=0;l<5;l++)
    {
        int xx=x+dx[l];
        int yy=y+dy[l];
        if(xx>=0&&xx<5&&yy>=0&&yy<5)//控制边界范围
        a[xx][yy] ^= 1;//对1这个位置的灯做相反操作
    }
}
int slove()
{
    ans=INF;
    for(k=0;k < 1<<5;k++)//一共只有32种状态对每种状态枚举递推
    {
        int res=0;
        memcpy(cpy,a,sizeof a );
        for(j=0;j<5;j++)
        {
            if(k>>j&1)//取出k的第j位就是相当于取出第几盏灯的状态
            {
                res++;
                turn(0,j);
            }
        }
        for(i=0;i<4;i++)
        {
            for(j=0;j<5;j++)
            {
                if(a[i][j]=='0')
                {
                    res++;
                    turn(i+1,j);//第i行的状态只能由第i+1行得到
                }
            }
        }
        bool flag=true;
        for(j=0;j<5;j++)
        {
            if(a[4][j]=='0')
            {
                flag=false;
                break;
            }
        }
        if(flag)
            ans=min(ans,res);//在每次的状态中寻找最小值
        memcpy(a,cpy,sizeof cpy );
    }
    if(ans>6)
        ans=-1;
    return ans;
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
       for(i=0;i<5;i++)
        scanf("%s",a[i]);
         slove();
       cout<<ans<<endl;
    }
  return 0;
}

标签：状态,第一行,int,费解,开关,枚举,ans,include,递推
From： https://blog.51cto.com/u_15952369/6036914