The second session of question swiping and clock out activity -- solving the switching problem with recursion as the background (III)

Title Description

source ：acwing
Original title transmission gate

Problem solving report

Understanding of topic meaning

First of all to see switch Two words , Some friends may wonder if they can solve the problem with the switch model in recursion . Recall the characteristics of previous switch exercises that can use recursion ： Whether their switch is on or off is caused by some conditions that they must be pressed .

But for this problem , You can't do this , Because too many switches are involved , There is no such case that the switch pressing method can be uniquely determined .

At this time, observe the data range , I found that it only had 4 individual , Then we can estimate whether the lovely violence enumeration can work , Roughly determine the time complexity by calculating the number of operations .

16 Switches , Only open or not open , So the total is from 0 Enumerate to $2^{16}-1$, That is to say 65536 In this case . Remember each of these situations , We all see one 16 Bit binary number , To imitate the chessboard . If the binary number corresponding to a certain position is 0 Just press , yes 1 Just don't press

The first enumeration in the inner layer ：
Here 65536 In these cases , You still need to enumerate each time 16 Is the position to be opened or closed , Each switch operates a maximum of seven surrounding bulbs .

The second enumeration in the inner layer ：
And enumerate to check whether the status of each bulb is all turned on , And the final recording scheme , So the approximate number of operations is $65536\ast (16\ast 7+16+16)$

About 10 million operations .C++ One second is about 1 100 million times , No problem .

About dictionary order

From top to bottom in the title , The order from left to right is actually the dictionary order .

It's easy to solve this problem , As long as we enumerate in dictionary order , That is to say, the enumeration sequence is from small to large , The final result must be in dictionary order .

Implementation process

First step ： enumeration 65536 Kind of plan .
The second step ： According to this scheme 16 One bulb for operation .
The third step ： Judge whether all bulbs are on after operation , If it's all on , Record the plan . Because the minimum number of steps is required , Then every time you find a solution, you should compare it with the previous solution .

details

One 、 Backup and restore backup
Two 、 In the output answer , The starting point is (1,1). The end is (4,4). Because we created the map from 0 At the beginning , So we need to The output results are +1

Reference code

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

#define x first
#define y second

using namespace std;
typedef pair<int,int> PII;
const int N = 5;
int n;
char g[N][N],backup[N][N];

int get(int x,int y)
{
    return 4 * x+ y;
}

void turn_one(int x,int y)
{
    if(g[x][y] == '+') g[x][y] = '-';
    else g[x][y] = '+';
}

void turn_all(int x,int y)
{
    for(int i = 0; i < 4;i++)
    {
        turn_one(x,i);
        turn_one(i,y);
            
    }
    //（x,y） One more press , Press back 
    turn_one(x,y);
}

int main()
{
    // Enter the chessboard 
    for(int i = 0; i <  4;i++) cin >> g[i];
    
    // Record the final answer 
    vector<PII> res;
    // enumeration 2^16 Kind of plan 
    for(int op = 0; op < 1 << 16;op++)
    {
        
        vector<PII> temp;
        // Make a backup 
        memcpy(backup,g,sizeof g);
        // Enumerate each switch 
        for(int i = 0; i < 4;i++)
            for(int j = 0; j < 4;j++)
            if(!(op >> get(i,j)&1)) //get(i,j) This function is used to determine the current position in the map by coordinates 0~15 Which number in 
            {
                temp.push_back({i,j});
                turn_all(i,j);// change i That's ok j All of the columns, etc 
            }
    
        bool has_closed = false;    
        // Judge whether all the etc. are bright 
        for(int i = 0; i < 4;i++)
            for(int j = 0; j < 4;j++)
            {
                if(g[i][j] == '+')  has_closed = true;
            }
        
        // Record the plan 
        if(!has_closed) 
        // If the array used to store the answers is empty , Or the number of stored steps is larger than that of the new test , Just update res
            if(res.empty() || res.size() > temp.size()) res = temp;
        
        // Restore backup 
        memcpy(g,backup,sizeof backup);
    }
    
    cout << res.size() << endl;
    // Note that the title is from 1 At the beginning 
    for(auto r:res) cout << r.x+1 << ' ' << r.y+1<<endl;
}

summary

So far, , The switch problem with recursion as the background comes to an end .

As far as my current understanding is concerned , If you encounter switch problems, you can first go to the manual simulation example , See if it can be pushed down . If you can , That's the best , If not , Then you can also consider pulling out a lovely search