解法一:bfs + 状态压缩
解法二:递推
- 对每个位置,只会有一次操作,因为如果两次操作则回到原来的状态(无意义),三次操作结果与第一次相同;
- 一组使灯全亮的开关灯操作序列是无序的,即哪个位置先操作都无所谓,最终都会达到全亮状态;
根据上面两条原则,可以通过递推的方式求解。
当第一行的某一列为 0
时,只能通过操作下一行的同一列使其变为 1
;即 g[i][j] == '0
时,需要改变 g[i + 1][j]
使其变为 1
, 以此类推。
故需要确定第一行的状态,然后递推第二行、第三行,直到第 $n$ 行,此时第 $n$ 行无法通过第 $n + 1$ 行来改变,故判断第 $n$ 行是否为 1
,即可确定是否可以通过初始状态改变到全为 1
的状态。
第一行有五列,即有 $2^5$ 种初始状态,枚举每种初始状态,再判断是否能在限制的步数内完成转换。
时间复杂度 $O(2^5 * 20 * 5 * 500)$
- 第一行初始状态共 $2^5$ 种
- 前四行共有 $20$ 种操作的可能
- 每次操作需要修改 $5$ 个位置
- 输入的数据量最多为 $500$ 组
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
#define it insert
#define pob pop_back
#define pub push_back
#define emb emplace_back
#define all(v) (v).begin(), (v).end()
#define mkp(a, b) make_pair(a, b)
using LL = long long;
using VI = vector<int>;
using VVI = vector<vector<int>>;
using PII = pair<int, int>;
using PIL = pair<int, LL>;
using PLL = pair<LL, LL>;
const double EPS = 1e-4;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int N = 1e5 + 7;
int ans;
char g[7][7];
const int dx[] = {0, -1, 0, 1, 0}, dy[] = {0, 0, 1, 0, -1};
void turn(int x, int y) {
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) {
g[a][b] ^= 1;
}
}
}
int solve() {
int ans = INF;
for (int k = 0; k < 1 << 5; ++k) {
int cnt = 0;
char back[7][7];
memcpy(back, g, sizeof g);
for (int i = 0; i < 5; ++i) {
if (k >> i & 1) {
++cnt;
turn(0, i);
}
}
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;
break;
}
}
if (flag) ans = min(ans, cnt);
memcpy(g, back, sizeof back);
}
return ans;
}
int main() {
int t;
cin >> t;
while (t--) {
for (int i = 0; i < 5; ++i)
cin >> g[i];
int ans = solve();
if (ans > 6)
cout << -1;
else
cout << ans;
}
return 0;
}