费解的开关

这题做法很简单，首先考虑什么情况下需要摁开关，因为每次摁开关都会导致十字区域的开关状态变，因此，当第 i 行第 j 列的开关是关的情况下，才需要摁第 i+1 行第 j 列的开关

假如第一行固定的情况下，例如第一行是 11011，那么第二行的第 3 列就必须摁一下，此时第一行变成了 11111。因为第二行中某一个摁了一下，导致第二行发生变化，例如变成 01011，那么第三行就需要摁第 1 列和第 3 列的开关，此时第二行也变成了 11111，一直下去

上面说的是第一行固定的情况，但是第一行也是可以摁的，并且摁的方法数有 $2^5$ 种，所以需要先对第一行开关摁的情况进行一个枚举，然后再递推后面所有行的情况

这里要注意的是，由于最后一行没有下一行，所以最后一行的状态是无法改变的，当我们从上往下摁到最后一行的时候，需要判断最后一行是否是全 1 的状态，如果是，就更新摁的次数（每次取最小值）

import java.util.Scanner;

public class Main {
    static int[][] map = new int[5][5];
    static int[][] move = {{0, 0}, {0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int T = cin.nextInt();
        while ((T--) != 0) {
            for (int i = 0; i < 5; i++) {
                String tmp = cin.next();
                for(int j = 0; j < 5; j++)
                    map[i][j] = tmp.charAt(j) - '0';
            }
            System.out.println(dfs());
        }
    }
    
    static int dfs() {
        int ans = Integer.MAX_VALUE >> 1;
        for (int i = 0; i < (1 << 5); i++) {
            int sum = 0;
            int[][] copy = new int[5][5];
            for (int row = 0; row < 5; row++)
                for (int col = 0; col < 5; col++)
                    copy[row][col] = map[row][col];
            for (int j = 0; j < 5; j++)
                if ((i >> j & 1) == 1) {
                    sum++;
                    change(0, j);
                }
            
            for (int k = 0; k < 4; k++) // 最后一行不摁
                for (int col = 0; col < 5; col++)
                    if (map[k][col] == 0) {
                        sum++;
                        change(k + 1, col);
                    }
            boolean flag = true;
            for (int col = 0; col < 5; col++)
                if (map[4][col] == 0) {
                    flag = false;
                    break;
                }
            if (flag)
                ans = Math.min(ans, sum);
            for (int row = 0; row < 5; row++)
                for (int col = 0; col < 5; col++)
                    map[row][col] = copy[row][col];
        }
        return ans <= 6 ? ans : -1;
    }
    
    static void change(int x, int y) {
        for (int i = 0; i < 5; i++) {
            int nx = x + move[i][0];
            int ny = y + move[i][1];
            if (nx < 5 && nx >= 0 && ny < 5 && ny >= 0)
                map[nx][ny] ^= 1;
        }
    }
}