题目描述

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

样例

3
00111
01011
10001
11010
11100

11101
11101
11110
11111
11111

01111
11111
11111
11111
11111

算法

递归剪枝$

当我们拿到这道题的时候，就知道这道题一定是需要用暴力求解的，从这道题我们可以得到如下几个信息：
+ 1.必须一行一行解决，也就是从第0行到第4行进行求解
+ 2.每个开关只能被按下0或1次，如果按下两次等于没按
+ 3.灯的状态和按下的开关之间可以进行xor操作（下面会详细说）

首先最简单的就是读入操作，为了后序更方便的进行位运算，我们这里用一个数组

int lightState[5];      //灯的状态

来保存灯的状态，每一个元素代表一行，我们只需要前五位，接着读入数据：

#define lightCal(i,j) ((light[i][j] - '0')<< (4-j))
int lightState[5];      //灯的状态
int main(int argc, const char** argv) 
{
    //读入数据
    int times;
    char light[5][5];
    cin >> times;
    while(times--)
    {
        for(int i = 0;i < 5;i++)
        for(int j = 0;j < 5;j++)
            cin >> light[i][j];

        for(int i = 0;i < 5;i++)
        {
            lightState[i] = lightCal(i,0) + 
            lightCal(i,1) + lightCal(i,2) 
            + lightCal(i,3) + lightCal(i,4);
        }
    }
    return 0;
}

这样，每个元素都表示一行的状态了，方便我们做后序的位运算。
有了数据之后，我们要来写递归程序了：
首先我们从第一行开始，我们定义灯的开关状态为i，比如在第一行中，5个灯的开关状态共有32种，我们可以认为开关是否被按下的状态对应的就是i的二进制，1代表按下开关，0代表没有，因此：
（其中的一些函数下面会详细介绍。）

    //每一行的每一位，都有按和不按两种选择
    for(int i = 0;i < 1<<5;i++)//i为开关灯操作
    {
        //做i操作的步数
        int needTurnTime = calClickTime(i);//计算i二进制中1的个数（也就是按下了多少个开关）
        if(curN + needTurnTime > maxN)continue;//不走这一步，不能超过6步或者已经找到的步数
        clickLight(row,i);  //打开开关，改变lightState的值
        curN += needTurnTime;
        answer(row + 1);    //下一行看看
        curN -= needTurnTime;
        clickLight(row,i);//恢复之前开灯的状态（按下两次会变成之前状态）
    }

写完如上递归程序后，还要写出口条件(灯全亮就是11111，也就是(1 << 5) - 1)：
(ifTrue()函数用来判断最终的lightState是否全1)

    //如果当前行的上两行有0，无需递归下去
    if(row > 1 && lightState[row-2] != (1<<5)-1)return;
    if(row == 5)//如果找到解
    {
        if(ifTrue())maxN = curN,lookForAnswer = true;
        return;
    }

好的，那么详细的来介绍开灯的函数clickLight(int row,int value):

//对于某一行开灯操作，上下行也会因此被影响，上下行的状态转换取决于这一个点按了没有
//因此，对于上一行来说，lightState[row-1] ^= value;
//而下一行为：if(row < 4)lightState[row+1] ^= value;
//因为按下某个点同样会影响左右两个点，因此我们定义两个值lvalue和rvalue
//lvalue将value左移，但因为左移会使得第六位有值，因此要&((1<<5)-1)
//rvalue同理，但是&((1<<5)-1)只是为了好看，没什么作用
//接着做xor操作，lightState[row] ^= lvalue ^ rvalue ^ value;
//上面的操作需要读者好好悟一悟，我个人觉得还是写的漂亮的
void clickLight(int row,int value)
{
    //上下左右都会改变
    if(row > 0)lightState[row-1] ^= value;
    if(row < 4)lightState[row+1] ^= value;
    int lvalue = (value << 1)&((1<<5)-1);
    int rvalue = (value >> 1)&((1<<5)-1);
    lightState[row] ^= lvalue ^ rvalue ^ value;
}

下面讲讲calClickTime操作，就是计算一个值value里有多少个1，感兴趣的百度一下lowerbit操作，这里直接贴上代码：

int calClickTime(int value)
{
    int num = 0;//计算value二进制中有几个1，相当于按下几次开关
    while(value!= 0)num++,value -= value & (-value);
    return num;    
}

因此，全部代码如下：

#include <iostream>
#include <vector>
#include <bitset>
using namespace std;
#define lightCal(i,j) ((light[i][j] - '0')<< (4-j))

void answer(int row);
bool ifTrue(void);
void clickLight(int row,int value);
int calClickTime(int value);
int lightState[5];      //灯的状态
int maxN = 6;//当前最大解
int curN = 0;//当前步数
bool lookForAnswer = false;//是否找到了解
int main(int argc, const char** argv) 
{
    //读入数据
    int times;
    char light[5][5];
    cin >> times;
    while(times--)
    {
        for(int i = 0;i < 5;i++)
        for(int j = 0;j < 5;j++)
            cin >> light[i][j];

        for(int i = 0;i < 5;i++)
        {
            lightState[i] = lightCal(i,0) + 
            lightCal(i,1) + lightCal(i,2) 
            + lightCal(i,3) + lightCal(i,4);
        }
        lookForAnswer = false;
        curN = 0,maxN = 6;
        answer(0);
        if(lookForAnswer)cout << maxN << endl;
        else cout << -1 << endl;
    }
    return 0;
}

//按下这个开关后的解:规定1为按下开关

void answer(int row)
{
    //如果当前行的上两行有0，无需递归下去
    if(row > 1 && lightState[row-2] != (1<<5)-1)return;
    if(row == 5)//如果找到解
    {
        if(ifTrue())maxN = curN,lookForAnswer = true;
        return;
    }
    //每一行的每一位，都有按和不按两种选择
    for(int i = 0;i < 1<<5;i++)//i为开关灯操作
    {
        //做i操作的步数
        int needTurnTime = calClickTime(i);
        if(curN + needTurnTime > maxN)continue;//不走这一步
        clickLight(row,i);  //打开开关
        curN += needTurnTime;
        answer(row + 1);    //下一行看看
        curN -= needTurnTime;
        clickLight(row,i);//恢复之前开灯的状态（两次会变成之前状态）
    }
}

bool ifTrue(void)
{
    for(int i = 0;i < 5;i++)
        if(lightState[i] != (1<<5)-1)return false;
    return true;
}

int calClickTime(int value)
{
    int num = 0;//计算value二进制中有几个1，相当于按下几次开关
    while(value!= 0)num++,value -= value & (-value);
    return num;    
}

void clickLight(int row,int value)
{
    //上下左右都会改变
    if(row > 0)lightState[row-1] ^= value;
    if(row < 4)lightState[row+1] ^= value;
    int lvalue = (value << 1)&((1<<5)-1);
    int rvalue = (value >> 1)&((1<<5)-1);
    lightState[row] ^= lvalue ^ rvalue ^ value;
}

时间复杂度

从图中我们可以知道，递归的深度不会超过5步，因为我是以行来做的递归，而且在里面还做了比较猛的剪枝，包括按下灯的开关的数量不能超过maxN，而且随着求解过程的进行，可能会找到一个新的解，解的大小要小于6，那么此时maxN被更新为最短解的值，后续剪枝力度更大