当前位置：网站首页>Puzzling switch

Puzzling switch

2022-07-20 23:08:00 【Ding Jiaxiong】

subject

You played “ Pull light ” Games ？

25 The lamps are arranged in a row 5×5 The square of .

Every light has a switch , Players can change its state .

Each step , Players can change the state of a certain light .

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 .
We use Numbers 1
It means an open light , Use numbers 0 It means the light is off .

The following state

After changing the state of the lamp in the top left corner, it will become ：

After changing the lamp in the middle, the state will become ：

Given some initial state of the game , Write a program to determine if the player is likely to be in 6 Make all the lights on in step .
Input format

Enter a positive integer in the first line n, There are n The initial state of the game to be solved .

The following lines of data are divided into n Group , Each group of data has 5 That's ok , Each row 5 Characters .

Each set of data describes the initial state of a game .

Each group of data is separated by a blank line .
Output format

Total output n Row data , Each line has one less than or equal to 6 The integer of , It means that it takes at least a few steps for the corresponding game state in the input data to make all the lights on .

For the initial state of a game , if 6 You can't turn all the lights on in steps , The output −1.
Data range

0<n≤500

sample input ：

sample output ：

3
2
-1

Thought analysis

Insert picture description here

Answer key

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;

const int N = 6; 
char g[N][N],backup[N][N];
// Define offset 
int dx[5] = {
    -1,0,1,0,0},dy[5] = {
    0,1,0,-1,0};
void turn(int x ,int y ){
    
    for(int i = 0; i < 5; i++){
    
        // The offset position 
        int a = x + dx[i];
        int b = y + dy[i];
        if (a < 0 || a >= 5 || b < 0 || b >= 5){
    
            continue; // Direct to ignore 
        }
        g[a][b] ^= 1; // Exclusive or operation , take 0 change 1,1 change 0
    }
}
int main(){
    
    int T; // Number of test data 
    cin >> T;
    while(T --){
    
        // Read into chessboard 
        for(int i = 0; i < 5 ; i++){
    
            cin >> g[i];
        }
        // Record the steps 
        int res = 10;
        // Enumerate the operations on the first line 
        for(int op = 0; op < 32;op ++){
    
            // Backup 
            memcpy(backup , g , sizeof g);
            int step = 0;
            // Switch light operation 
            for(int i = 0 ; i < 5 ; i++){
    
                if (op >> i & 1){
    
                    step ++;
                    turn(0,i);
                }
            }
            // The rest of the line 
            for(int i = 0; i < 4 ;i++){
     // That's ok 
                for(int j = 0; j < 5 ;j ++ ){
     //  Column 
                    if(g[i][j] == '0'){
    
                        step ++;
                        turn(i + 1,j);
                    } 
                }
            }
            bool dark = false;
            // Judge whether there is any light on the last line 
            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);
        }
        if(res > 6){
    
            res = -1;
        }
        cout << res << endl;
    }
    return 0;
}