从零开始学算法-Day6

//2020.4.27

题目：费解的开关

题目描述：

链接：https://ac.nowcoder.com/acm/contest/998/D
来源：牛客网

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

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

10111
01101
10111
10000
11011

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

01111
11101
10111
10000
11011

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

01111
11001
11001
10100
11011

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

求解之路；

如果能6步全亮，那么从第一排开始，对其进行枚举，然后一次次得改变，看最后一行能否全亮

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>

using namespace std;
const int INF = 1e6; 
int T;
char a[5][5],dx[5]={0,0,-1,0,1},dy[5]={0,1,0,-1,0};
//a数组用来存每次的情况，dx,dy是为了方便每一次改变对其上下左右得灯的状态
void turn(int x,int y){//改变灯的状态 
    int xi,yi;
    for(int i = 0;i < 5;i ++)
    {
        xi = x+dx[i];yi = y+dy[i];
        if(xi >= 0 && xi < 5 && yi >= 0 && yi < 5)
            a[xi][yi] ^= 1;//通过异或运算 ，将其置为相反 
     } 
}
int work()
{
    int ans = INF;
    for(int k = 0; k < 1 << 5; k++)//枚举第一行的所有情况
    {
        int cnt = 0;//操作次数
        char temp[5][5];//保存数组
        memcpy(temp, a, sizeof a);

        for(int i = 0; i < 5; i++)//将当前a数组的情况转化为k枚举到的情况
            if(k >> i & 1)
            {
                cnt++;
                turn(0, i);
            }

        for(int i = 0; i < 4; i++)//前4行5列
            for(int j = 0; j < 5; j++)
                if(a[i][j] == '0')//如果是灭的
                {
                    cnt++;
                    turn(i + 1, j);//操作它下方的当，使它变亮
                }

        bool is_ok = true;  
        for(int i = 0; i < 5; i++)//检查最后一行是否全亮
        {
            if(a[4][i] == '0')
            {
                is_ok = false;
                break;
            }
        }
        if(is_ok)
            ans = min(ans, cnt);

        memcpy(a, temp, sizeof a);//恢复现场，将a数组回复
    }
    if(ans > 6)
        ans = -1;
    return ans;
}
int main(){
    cin >> T;
    while(T--){
        for(int i = 0;i < 5;i++)
            for(int j = 0;j < 5;j++){
                cin >> a[i][j];
            }
       cout << work() << endl;;
    }
    return 0;

}

代码来源：https://www.acwing.com/activity/content/code/content/24514/

学不进去了啊！！！ 太难了吧