[Acwing 95] puzzled switch – enumeration + search

(The title is from ACwing)

Have you played the “pull the light” game? The 25 lights are arranged in a 5×5 square. Each light has a switch, and the player can change its state. At each step, the player can change the state of a certain light. The player changing the state of a light will have a chain reaction: the lights adjacent to the light up, down, left, and right will also change their states accordingly.

We use the number “1” to indicate an on light, and the number “0” to indicate an off light.

Given the initial state of some games, write a program to determine whether the player can turn on all the lights within 6 steps.

Input format

Enter a positive integer in the first linen

“>n< /span>, which means there are n

“> nThe initial state of the game to be solved.

The following rows of data are divided into n“>n groups, each group of data has 5 rows and each row has 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

“>n< /span> line data, each line has an integer less than or equal to 6, which means that it takes at least a few steps for the corresponding game state in the input data to enable all lights Brighten.

For a certain initial state of the game, if all the lights cannot be turned on within 6 steps, “-1” will be output.

The essence of the question is: to solve the minimum number of steps required to transform a 5 * 5 01 square matrix into a square matrix composed of only 1 through the above operation. If you simply enumerate the changed points every time to search, the size of the state space cannot be tolerated, which obviously does not work.

　　 Actually, the transformation given in the question has two very important properties. First, each point is transformed at most once, because repeated operations are invalid; second, different sequences of the same operations will not affect the final result, because the cumulative effect at each position is the same.

　　From these two points, we found that we can enumerate some transformations to recursively all operations. Specifically, consider performing the transformation line by line, then the transformation performed by all lines above the current line i has been determined; if there is 0 at the kth position on the i-1th line, then only by changing the i-th line The k-th position makes the i-1th line legal, which is the key to solving this problem. Therefore, we can enumerate the 2^5 = 32 transformations performed in the first row in binary, and then recursively recursive operations on the second to fifth rows. Finally, check whether the fifth line is all 1s, and if the fifth line is valid, update the answer with the current number of steps.

　　The lesson learned from this question is to use the statement “ios::sync_with_stdio(0)” with caution, because this instruction cancels the compatibility of cin and C standard input and output. Once the hand slides, use cin at the same time. And getchar, scanf and other C library read functions will cause errors. It is best to consider the application of this sentence when you read the string, and you should usually read it by hand to avoid tragedy.

Code:

1. #include< /span>
2. #include
3. #include< iostream>
4. #include
5. #include
6. usingnamespacestd;
7. constint inf= 0x3f3f3f3f;
8. int sw[10][10], tmp[10][10], cnt, ans;
9. int addx[5 ] = {0, 0, 0, -1, 1}, addy[5] = {0, 1, -1, 0, 0};
10. void change(int x, int y, int a[10][10]) {< /span>
11. int tx, ty;
12. for (int i= 0; i< 5; ++i) {
13. tx = x + addx[i], ty = y + addy[i];

< li>if(a[tx][ty]==-1)continue;

14. a[tx][ty] = !a[tx][ty];
15. } ++cnt;

< li>}

16. void init(int x){
17. memcpy(tmp, sw, sizeof(tmp));
18. for(< span class="datatypes">int i = 1; i<= 5; ++i)
20. if(x>>( i- 1)& 1)
21. change(1, i, tmp);
24. int main(){
25. int T;
26. cin>> T;
27. while(T- -){
28. Ans = inf;
29. memset(sw, -1, sizeof(sw)) ;
30. char ch;
31. for (< span class="datatypes">int i = 1; i <= 5; ++i) {
32. while(!isdigit( ch))
33. ch = getchar();
34. for( int j = 1; j <= 5; ++j)
35. sw[i][j]= ch-48, ch= getchar( );
37. /* for (int i = 1; i<= 5;++i) {< /span>
38. for (int j = 1; j<= 5;++j)
39. cout<< sw[i][j]<<"";
40. cout<
41. */
42. for (int x= 0; x<32;++x){
43. cnt = 0;
44. init(x);

< li class="alt">for(int i= 2;i<=5;++i)

45. for(intj=1;j<=5;++j)
46. if (!tmp[i- 1][j])
47. Change(i, j,

>

48. for (int i= 1;i<= 5;++i)< /li>
49. if (!tmp[5][i]) cnt=inf;
50. = Min(ans, cnt);
52. if (ans<= 6)
53. Cout<< ans<
54. else puts(“-1”);“-1”); /span>
57. return 0;< /li>
58. }