解法一: BFS + 状态压缩

从全为 1 的状态开始，BFS 搜索6步以内的所有状态；

通过将 $5\times 5$ 的 $0,1$ 矩阵转化为 25 位二进制数进行状态压缩；

计算输入初始状态的二进制值，查表；

#include <iostream>
#include <queue>
#include <unordered_map>
using namespace std;

int n;
const int dx[] = {-1, 0, 1, 0, 0}, dy[] = {0, 1, 0, -1, 0};
unordered_map<int, int> mp;

int turn(int u, int i) {
    int x = i / 5, y = i % 5;
    for (int d = 0; d < 5; ++d) {
        int a = x + dx[d], b = y + dy[d];
        if (0 <= a && a < 5 && 0 <= b && b < 5) {
            u ^= 1 << (a * 5 + b);
        }
    }
    return u;
}

void bfs() {
    int x = (1 << 25) - 1;
    int cnt = 0;
    mp[x] = 1;
    queue<int> q;
    q.push(x);
    int ma = 0;
    while (!q.empty()) {
        auto p = q.front(); q.pop();
        if (mp[p] > 6) break;
        for (int i = 0; i < 25; ++i) {
            ++cnt;
            int t = turn(p, i);
            if (!mp.count(t)) {
                mp[t] = mp[p] + 1;
                q.push(t);
            }
        }
        ma = max(ma, (int)q.size());
    }
}

int main() {
    bfs();
    scanf("%d", &n);
    while (n--) {
        int x = 0;
        for (int i = 0; i < 25; ++i) {
            int a;
            scanf("%1d", &a);
            x += (a << i);
        }
        printf("%d\n", mp[x] - 1);
    }
    return 0;
}

复杂度分析

• 时间复杂度 $O({25}^5\*5*n)$，其中枚举 $25$ 个位置的状态 $5$ 轮（存在重复的情况，实际远小于此，共 $244582$ 种状态），每次操作需修改 $5$ 个位置，$n$ 是测试数据量。
• 空间复杂度 $O({25}^5)$，通过输出得队列中元素最多为 $176241$ 个，map 中最终状态 $244582$ 个。

解法二：位运算枚举 + 递推

首先这种 0 和 1 转换的问题有两点明确：
1. 每个位置只会有一次转换操作，因为如果两次操作则回到原来的状态（无意义），三次操作结果与第一次相同；
2. 一组满足要求的操作序列具有无序性，即操作序列中的任意两个操作，谁先谁后结果都相同。

根据上面两条原则，可以通过递推的方式求解。

当第一行的某一列为 0 时，只能通过操作下一行的同一列使其变为 1，如果通过改变当前位置则会影响到其他方向上的状态；即 g[i][j] == '0' 时，需要改变 g[i + 1][j] 使其变为 1， 以此类推。

故需要确定第一行的状态，然后递推第二行、第三行和第四行，此时第五行的状态已被确定，故判断第五行是否全为 1，即可确定是否可以通过初始状态改变到全为 1 的状态。

#include <iostream>
#include <cstring>
using namespace std;

const int N = 7;
int n;
char p[N][N], g[N][N];
const int dx[] = {-1, 0, 1, 0, 0}, dy[] = {0, 1, 0, -1, 0};

void turn(int x, int y) {
    for (int i = 0; i < 5; ++i) {
        int a = x + dx[i], b = y + dy[i];
        if (0 <= a && a < 5 && 0 <= b && b < 5) {
            g[a][b] = '0' + !(g[a][b] - '0');
        }
    }
}

int work() {
    int ans = 0x3f3f3f3f;
    for (int x = 0; x < 1 << 5; ++x) {
        int cnt = 0;
        memcpy(g, p, sizeof p);

        for (int j = 0; j < 5; ++j) {
            if (x >> j & 1) ++cnt, turn(0, j);
        }

        for (int i = 0; i < 4; ++i) {
            for (int j = 0; j < 5; ++j) {
                if (g[i][j] == '0') ++cnt, turn(i + 1, j);
            }
        }

        bool flag = 1;
        for (int j = 0; j < 5; ++j) {
            if (g[4][j] == '0') flag = 0;
        }
        if (flag) ans = min(ans, cnt);
    }
    return ans;
}

int main() {
    scanf("%d", &n);
    while (n--) {
        for (int i = 0; i < 5; ++i) scanf("%s", p[i]);
        int ans = work();
        printf("%d\n", ans > 6 ? -1 : ans);
    }
    return 0;
}

复杂度分析

• 时间复杂度 $O(2^5\*20\*5*N)$，其中第一行的初始状态共 $2^5$ 种，前四行共 $20$ 种可能的操作，每次操作需修改 $5$ 个位置，$N$ 是测试数据量。
• 空间复杂度 $O(1)$，保存初始状态的数组为 $5*5$，忽略不计。