題目
傳送門
題解
枚舉第一行的狀态,然後向下搜尋按題意模拟即可
code
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <cctype>
#include <cstdio>
#include <bitset>
#include <string>
#include <vector>
#include <complex>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <functional>
#define l(x) t[x].l
#define r(x) t[x].r
#define sum(x) t[x].sum
#define add(x) t[x].add
#define clean(x, y) memset(x, y, sizeof(x))
const int maxn = 5e5 + 100;
const int inf = 0x3f3f3f3f;
const int dir[5][2] = { 0, 0, 1, 0, -1, 0, 0, 1, 0, -1 };
typedef long long LL;
using namespace std;
template <typename T>
inline void read(T &s) {
s = 0;
T w = 1, ch = getchar();
while (!isdigit(ch)) { if (ch == '-') w = -1; ch = getchar(); }
while (isdigit(ch)) { s = (s << 1) + (s << 3) + (ch ^ 48); ch = getchar(); }
s *= w;
}
template<typename T>
inline void write(T s) {
if (s < 0) putchar('-'), s = -s;
if (s > 9) write(s / 10);
putchar(s % 10 + '0');
}
int n;
int m;
int ans;
int res;
int a[7][7];
int g[7][7];
bool flag;
inline void turn(int x, int y) {
for (int k = 0; k < 5; ++k)
g[x + dir[k][0]][y + dir[k][1]] ^= 1;
}
int main() {
read(n);
while (n--) {
for (int i = 1; i <= 5; ++i) {
for (int j = 1; j <= 5; ++j) {
char ch;
cin >> ch;
a[i][j] = (int)(ch - '0');
}
}
ans = inf;
for (int k = 1; k <= 32; ++k) {
for (int i = 1; i <= 5; ++i)
for (int j = 1; j <= 5; ++j)
g[i][j] = a[i][j];
res = 0;
for (int i = 0; i < 5; ++i) {
if ((k >> i) & 1) {
++res;
turn(1, i + 1);
}
}
for (int i = 2; i <= 5; ++i) {
for (int j = 1; j <= 5; ++j) {
if (g[i - 1][j] == 0) {
++res;
turn(i, j);
}
}
}
flag = true;
for (int i = 1; i <= 5; ++i) {
if (g[5][i] == 0) {
flag = false;
break;
}
}
if (flag)
ans = min(ans, res);
}
if (ans > 6) ans = -1;
write(ans), putchar('\n');
}
return 0;
}