算法分析

递推
目标是把所有开关全部变成1，由于当上一行的状态确定时，若上一行存在0的状态，只能由下一行的位置去影响上一行的0，因此可以使用递推

• 1、只要第0行开关的状态确定，则所有开关的状态都可以递推出来，因此枚举第一行状态的所有情况，总有32种情况,
• 2、从第0行递推出第1到第4行的状态，若当前行状态已确定，且存在一个开关是0状态，则需要下一行的位置对开关进行切换，影响当前行开关是0的状态
• 3、最后枚举最后一行（第4行）若该状态全部是1，则表示成功，更新最小步数

时间复杂度 $O(2^5 * 25 * 5 * 500)$

2^5表示第0行操作的状态，25表示最多操作的点，5表示操作一个需要更新5个位置的状态，500表示有500的样例

参考文献

算法提高课

Java 代码

import java.util.Scanner;

public class Main {
    static int N = 6;
    static int[][] bg = new int[N][N];
    static int[][] g = new int[N][N];
    static int[] dx = new int[] {0,-1,0,1,0};
    static int[] dy = new int[] {-1,0,1,0,0};
    static void trun(int x,int y)
    {
        for(int i = 0;i < 5;i ++)
        {
            int a = x + dx[i];
            int b = y + dy[i];
            if(a < 0 || a >= 5 || b < 0 || b >= 5) continue;
            g[a][b] ^= 1;
        }
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        while(n -- > 0)
        {
            int res = 10;

            for(int i = 0;i < 5;i ++)
            {
                String s = scan.next();
                for(int j = 0;j < 5;j ++)
                    bg[i][j] = s.charAt(j) - '0';
            }
            //枚举所有情况
            for(int op = 0;op < 1 << 5;op ++)
            {
                int cnt = 0;
                //取出备份
                for(int u = 0;u < 5;u ++)
                    for(int v = 0;v < 5;v ++)
                        g[u][v] = bg[u][v];

                //操作第0行开关
                for(int i = 0;i < 5;i ++)
                    if((op >> i & 1) == 1)
                    {
                        trun(0,i);
                        cnt ++;
                    }

                //递推出第1到4行的状态
                for(int i = 0;i < 4;i ++)
                    for(int j = 0;j < 5;j ++)
                        if(g[i][j] == 0)
                        {
                            trun(i + 1,j);
                            cnt ++;
                        }

                //检查最后一行的灯是否全亮
                boolean success = true;
                for(int i = 0;i < 5;i ++)
                    if(g[4][i] == 0)
                        success = false;
                if(success && res > cnt) res = cnt;
            }

            if(res > 6) res = -1;
            System.out.println(res);
        }

    }
}