The second session of the question swiping and punching activity -- solving the switching problem with recursion as the background (I)

Title Description

source ：acwing
Original title transmission gate

Problem solving report

One 、 Understanding of topic meaning

Players change the state of a light and have a chain reaction ： And this lamp up and down adjacent to the left and right lights should also change their state accordingly .

Use windows Own drawing , Hold on shift Drag the mouse to draw the following graphics for demonstration .

Sample demonstration ：

Two 、 The operation of each line of switch is completely determined by the light on and off of the previous line

1. Suppose all the states in the first row are determined by enumeration , Each switch is either pressed , Or don't press , Here it is $2^5$ Secondary selection .
2. According to the light off state of the previous line , Decide how to press the next line , To ensure that the previous line is bright .
   

3、 ... and 、 The details are finalized

1. How to enumerate the first line 32 In the operation . A five bit binary can just represent this 32 Kind of operation . such as

11010 => Corresponding to the first 26 Operations . that 0 ~ $2^5$-1 You can enumerate the first row one by one 32 Kind of plan

2. Switch on function
   After clicking the switch in one position , Its four position switches will be changed . Use four $if$ It seems too troublesome . What is considered here is to add Offset implementation .
   

3. Time complexity
   $32\ast 25\ast 5\ast 500=2000000$, About twomillion calculations . There is no problem at all

Reference code

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

using namespace std;

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

// completion turn  function 
void turn(int x,int y)
{
    for(int i = 0; i < 5;i++)
    {
        int a = x+dx[i] , b = y + dy[i];
        // Judgement boundary 
        if(a < 0 || a >= 5 || b < 0 || b>= 5) continue;
        // Update status 
        g[a][b] ^= 1;
    }
}

int main()
{
    int T;
    cin >> T;
    
    while(T--)
    {
        // Building maps 
        for(int i = 0; i < 5;i++) cin >> g[i];
        
        int res = 10;// Record answer 
        // Enumerate the first line of 32 A choice 
        for(int op = 0; op < 32;op++)
        {
            memcpy(backup,g,sizeof g);
            int step = 0;// Record the steps performed 
            // Deal with whether there is a light that can be pressed on in the current scheme 
            for(int i = 0; i < 5; i++)
            {
                if(!(op >> i &1))
                {
                    step ++;
                    turn(0,i);
                }
            }
            
            // According to the current situation in the first line , Deal with the processing of the next four lines 
            for(int i = 0; i < 4;i++)
            {
                for(int j = 0; j < 5;j++)
                if(g[i][j] == '0') 
                {
                    step ++;
                    turn(i+1,j);
                }
            }
            
            // Traverse the last line , If there is a black lamp , Then the current scheme fails 
             bool dark = false;// Mark 
            for(int i = 0; i < 5;i++)
                if(g[4][i] == '0')
                {
                    dark = true;
                    break;
                }
            if(!dark) res = min(res,step);
            memcpy(g,backup,sizeof g);// Get the data back from the backup 
        }
            
            if(res > 6) res = -1;//res = -1 Represents no solution 
            
            cout << res << endl;
        
    }
    return 0;
}