AcWing 95. 费解的开关-----注释详细
原题链接
中等
作者:
会飞的泡泡
,
2021-01-18 21:56:21
,
所有人可见
,
阅读 329
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 6;
char g[N][N], backup[N][N];//备份数组用来还原原数组
int dx[5] = {-1,0,1,0,0}, dy[5] = {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 (a<0||a>=5||b<0||b>=5) continue; // 在边界外,直接忽略即可
g[a][b] ^= 1;
}
}
int main()
{
int T;
cin >> T;
while (T -- )
{
for (int i = 0; i < 5; i ++ ) cin >> g[i];
int res = 100;
for (int op = 0; op < 32; op ++ )
{
memcpy(backup, g, sizeof g);//把g拷贝给backup
int step = 0;
for (int i = 0; i < 5; i ++ )//枚举第一行(用二进制方法枚举)!!!得记住这个方法
if (op >> i & 1)
{
step ++ ;
turn(0, i);
}//turn第一行
for (int i = 0; i < 4; i ++ )
for (int j = 0; j < 5; j ++ )//对后面的行
if (g[i][j] == '0')
{
step ++ ;
turn(i + 1, j);
}
bool dark = false;
for (int i = 0; i < 5; i ++ )//判断最后一行
if (g[4][i] == '0')
{
dark = true;
break;
}
if (!dark) res = min(res, step);//如果最后一行是亮的更新res
memcpy(g, backup, sizeof backup);//操作的原数组!从备份中拷贝一份过来
}
if (res > 6) res = -1;
cout << res << endl;
}
return 0;
}