95.费解的开关

95.费解的开关

用枚举的思想，把第一行先枚举了

（通过：

for (int op = 0; op < 32; op ++ )for (int i = 0; i < 5; i ++ )if (op >> i & 1)

）

根据第i行去trun第i+1行来改变第i行

trun的改变利用了偏移量来简化

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;const int N = 6;
char g[N][N], backup[N][N];
int dx[] = {0, 0, 0, -1, 1}, dy[] = {0, -1, 1, 0, 0};void getg()
{for (int i = 0; i < 5; i ++ ) cin >> g[i];return;
}
void print()
{for (int i = 0; i < 5; i ++ ) cout << backup[i] << endl;cout << endl;return;
}
void bkup()
{memcpy(backup, g, sizeof g);// for (int i = 0; i < 5; i ++ ) backup[i] = g[i];return;
}void trun(int x, int y)
{int a, b;for (int i = 0; i < 5; i ++ ){a = x + dx[i], b = y + dy[i];if (a >= 0 && a < 5 && b >= 0 && b < 5) backup[a][b] ^= 1;}
}int main()
{int T;cin >> T;while (T -- ){getg();int ans = 10;// print();// 遍历第一行情况for (int op = 0; op < 32; op ++ ){// 第一行的一种情况bkup();int cnt = 0;for (int i = 0; i < 5; i ++ ){if (op >> i & 1){cnt++;trun(0, i);}}for (int i = 0; i < 4; i ++ ){for (int j = 0; j < 5; j ++ ){if (backup[i][j] == '0'){cnt++;trun(i + 1, j);}}}bool drak = false;for (int i = 0; i < 5; i ++ ) if (backup[4][i] == '0') drak = true;if (!drak) ans = min(ans, cnt);}if (ans > 6) ans = -1;cout << ans << endl;}return 0;
}