Title source AcWing.

The title

< P > Have you ever played “Pull the Light”? </p>

$25$lights arranged in a square of $5 \times 5$.

<p> Each light has a switch that allows the player to change its state. </p>

At each step, the player can change the state of a particular light.

<p> Players who change the state of a light have a chain effect: lights that are adjacent to the light, up, down, to the left, and to the right change their state accordingly. </p>

We use the number $1$to indicate a light that is on and the number $0$to indicate a light that is off.

<p> </p>

10111
01101
10111
10000
11011

<p> will become </p> after changing the state of the upper left corner light

01111
11101
10111
10000
11011

<p> and then change the light in the middle of it to: </p>

01111
11001
11001
10100
11011

Given some initial state of the game, write a program to determine whether it is possible for the player to turn on all the lights within $6$moves.

<h4> input format </h4>

In the first line, enter the positive integer $n$, which means that there are $n$of game initial states to be solved in the data.

The following rows of data are divided into $n$groups, with $5$rows per group and $5$characters per row.

<p> Each set of data describes the initial state of a game. </p>

<p> Each group of data is separated by a blank line. </p>

<h4> output format </h4>

Output a total of $n$rows of data, each row has an integer of less than or equal to $6$, which indicates that the corresponding game state in the input data requires at least a few steps to light up all the lights.

For an initial state of the game, if all lights cannot be turned on within $6$steps, then output $-1$.

<h4> Data range </h4>

  • $0 \le n \le 500$

<h4> input sample: </h4>

3 00111 01011 10001 11010 11100 11101 11110 11111 01111 11111 11111 11111

<p> output sample: </p>

3 2 1

Answer key

First, there are three very important properties that need to be explained:

  • If it’s determined by which lights, then it doesn’t matter what order the lights are in, it’s going to be the same no matter what order they’re in, right
  • There is no need to press a lamp twice or more, because two presses are equivalent to no presses, three presses are equivalent to two + one (that is, one)

Therefore:

  • Since it doesn’t matter what order the lights are in, we can press all the lights in the first row
  • We find that if I want to light all the lights in the first row, there is only one way I can press the lights in the second row, which is to press the lights below the lights that are not on in the first row (here is an example).
The first line state 10011 (1 represents the light on) the second action is 01100 (1 represents the button press)

So, how do we make sure that the second row is fully lit? Only use the third line to solve!

So, how do we make sure that the last row (the fifth row) is all lit up? There’s no guarantee!

We find that if the first line is fixed, then the next two, three, four, and five lines are all lit up.

Therefore, for any of the input states, we traverse the first line in all 32 ways to see which can be fully lit (by detecting the state of the fifth line), and whether any of these fully lit states have operations less than or equal to 6. If so, return the operand; otherwise, return -1.

code

#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 5 + 5; Char g[N][N]; char g[N][N]; char g[N][N]; char g[N][N]; Int dx[5] = {0, 1, 0, -1, 0}; int dx[5] = {0, 1, 0, -1}; int dy[5] = {1, 0, -1, 0, 0}; Void turn(int x, int y) {for (int I = 0; void turn(int x, int y); i < 5; ++ i) { int a = x + dx[i], b = y + dy[i]; if (0 <= a && a < 5 && 0 <= b && b < 5) g[a][b] = g[a][b] == '1' ? '0' : '1'; } } int work() { int ans = 2e9; G char backup[N][N]; g char backup[N][N]; g char backup[N][N]; memcpy(backup, g, sizeof g); for (int k = 0; k < (1 << 5); ++ k) {// make sure our g is the input g memcpy(g, backup, sizeof backup); // When the first action is k, the total number of operations is.. int res = 0; For (int j = 0; int j = 0; j < 5; ++ j) { if (k >> j & 1) { res ++; turn(0, j); }} for (int I = 0; int I = 0; int I = 0; int I = 0; int I = 0; i < 4; ++ i) { for (int j = 0; j < 5; ++ j) { if (g[i][j] == '0') { res ++; turn(i + 1, j); Bool success = true; bool success = true; bool success = true; bool success = true for (int j = 0; j < 5; ++ j) { if (g[4][j] == '0') { success = false; break; If (success) ans = min(res, ans); if (success) ans = min(res, ans); } if (ans > 6) return -1; return ans; } int main() { int n; cin >> n; while (n -- ) { for (int i = 0; i < 5; ++ i) cin >> g[i]; printf("%d\n", work()); }}