The Confounding Switches

Time Limit: C/C++ 1000MS, Other Languages 2000MS
Memory Limit: C/C++ 256MB, Other Languages 512MB

Description

Have you ever played the "Light Switch" game?
There are \(25\) lights arranged in a \(5×5\) grid.
Each light has a switch that can toggle its state.
In each move, a player can toggle one light's state.
When toggling a light, it also affects the adjacent lights (up, down, left, right).
We use digit \(1\) to represent an ON light and \(0\) for OFF.
Starting from this configuration:
\(10111\)
\(01101\)
\(10111\)
\(10000\)
\(11011\)
Toggling the top-left light results in:
\(01111\)
\(11101\)
\(10111\)
\(10000\)
\(11011\)
Then toggling the center light gives:
\(01111\)
\(11001\)
\(11001\)
\(10100\)
\(11011\)
Given initial configurations, write a program to determine whether all lights can be turned ON within 6 moves.

Input Description

The first line contains a positive integer \(n\), indicating the number of test cases.
The following lines contain \(n\) test cases, each consisting of 5 lines of 5 characters.
Each character represents a light's initial state (\(0\) or \(1\)).
Cases are separated by blank lines.

Output Description

Output \(n\) lines, each containing an integer between 0 and 6, representing the minimum steps required to turn all lights ON.
If it's impossible within 6 steps, output \(-1\).

Sample Input 1

3
00111
01011
10001
11010
11100

11101
11101
11110
11111
11111

01111
11111
11111
11111
11111

Sample Output 1

3
2
-1

Hint

\(0<n≤500\)

Code

Brute Force + Optimization + Memoization + Hashing Approach (\(\Large\textcolor{red}{\textrm{Brute Force for the Win!}}\))

See Luogu for details.

#include
#include
#include
using namespace std;

short dp[35000000];
inline int encode(bool grid[10][10])
{
	int result = 0;
	for(int i = 1; i