AcWing95. 费解的开关（/思维题）

原题
原题解

题目

约束

题解

#include<iostream>
#include<cstring>
using namespace std;
const int N = 11;
char g[N][N];
int dx[] = {0, -1, 0, 1, 0}, dy[] = {0, 0, 1, 0, -1};
void turn(int x, int y)//改变一整排的上下左右开关
{
    for(int i = 0; i < 5; i ++)
    {
        int a = x + dx[i], b = y + dy[i];
        if(a < 5 && a >= 0 && b < 5 && a >= 0)
        {
            g[a][b] ^= 1;//按位异或后赋值(同0异1)？？？‘0’-> 48-> 0011 0000 ‘1’-> 49-> 0011 0001  0000 0001 只改变最后一位
        } 
    }
}
int work()
{
    int ans = 0x3f3f3f3f, flag;
    for(int k = 0; k < (1 << 5); k ++)//k表示第一排所有按法
    {
        int step = 0; 
        char backup[N][N];
        memcpy(backup, g, sizeof g);//g中1表示亮着的，让每次试完之后可以回到初始位置
        for(int i = 0; i < 5; i ++)
        {
            if((k >> i) & 1)//k中1表示按下去
            {
                step ++;
                turn(0, i);
            }   
        }
        for(int i = 0; i < 4; i ++)
        {
            for(int j = 0; j < 5; j ++)
            {
                if(g[i][j] == '0')//前一排有暗的
                {
                    step ++;
                    turn(i + 1, j);//从第后一排开始按来影响前一排
                }
            }
        }
        flag = 1;
        for(int i = 0; i < 5; i ++)//只需要看最后一排是否全亮就能判断全部是不是亮着的
        {
            if(g[4][i] == '0')
            {
                flag = 0;
                break;
            }
        }
        if(flag) ans = min(step, ans);
        memcpy(g, backup, sizeof g);//很重要不要忘记写
    }
    if(ans > 6) return -1;
    else return ans;
}
int main()
{
    int n;
    cin >> n;
    while(n --)
    {
         for(int i = 0; i < 5; i ++) cin >> g[i];

         cout << work() << endl;
    }
    return 0;
}