95. 费解的开关

费解的开关"/>

95. 费解的开关

题目

思路

1. 因为最优解是每个灯只操作一次
2. 所以顺序无所谓
3. 只要确定了第一行后，下面都可以确定
4. 当前灯不亮就操作它下面的格子即可点亮它
5. 我觉得这种方法是唯一不会互相干扰的方法
6. 还是不太理解…

代码

#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
const int N = 10;char g[N][N];
int xx[5] = {0, 1, 0, -1, 0};
int yy[5] = {1, 0, -1, 0, 0};void turn (int x, int y)
{for (int i = 0; i < 5; i ++ ){int dx = x + xx[i];int dy = y + yy[i];if (dx < 0 || dx > 4 || dy < 0 || dy > 4) continue;g[dx][dy] ^= 1;}
}int main()
{int T; cin >> T;while (T -- ){for (int i = 0; i < 5; i ++ ) cin >> g[i];int ans = 0x3f3f3f3f;char backup[N][N];memcpy(backup, g, sizeof g);
//		只有每个灯按一遍才是最优解
//		确定第一行的各种按法为初始状态，剩下的都是为了点亮而点亮for (int op = 0; op < 31; op ++ ){int num = 0;memcpy(g, backup, sizeof backup);for (int i = 0; i < 5; i ++ ){if (op >> i & 1){turn (0, i);num ++;}}for (int i = 0; i < 4; i ++ ){for (int j = 0; j < 5; j ++ ){if (g[i][j] == '0'){turn(i + 1, j);num ++;}}}int f = 0;for (int i = 0; i < 5; i ++ ){if (g[4][i] == '0'){f = 1;break;}}if (!f){ans = min (ans, num);}}if (ans > 6) cout << -1 << endl;else cout << ans << endl;}return 0;
}