本题要点
这里先说明,看到很多写题解的人都理解错了,这里强调一点:并不是第一行的某个灯亮了就要按下去!
本题的递推不难理解,难理解的是表示第一行的所有状态,下面且听我一步步道来
这里用二进制表示一个状态,举个例子,k = 10001时是按第一行的第一个和最后一个
如果原始数据是这样的话
10111
01101
10111
10000
11011
那么按了k = 10001之后,这个状态就变成了
01100
11100
10111
10000
11011
按了第一行之后,根据第一行可以递推得出第二行和第五行,最后检查第五行是不是全1即可,这个很好理解
因此,本题的理解的难点在于表示按了第一行后的初始状态。
显然,第一行的按法有00000(一个也不按)到 11111(按了5个)共32种按法,只要将这每种按法都枚举一次,就可以得出第一行的所有状态
所以代码长这样
//0对应二进制的00000,31对应了11111,这样就可以枚举出所有的第一行状态了
//op只是一种按法的状态表示,用0表示按也是ok的,比如10001表示按第二,三,四个灯,但习惯性用1来表示按
for(int op = 0; op < 32; op++){
int cnt = 0;
memcpy(curStatus, backup, sizeof curStatus);
for(int i = 0; i < 5; i++){
//习惯性写法,第i位为1时,按第一行的第i个灯
if(op >> i & 1){
turn(0, i);
cnt++; //按一次次数就加1
}
}
}
完整代码
#include<cstdio>
#include<cstring>
using namespace std;
const int N = 6;
char curStatus[N][N];
int dx[5] = {-1, 0, 1, 0, 0};
int 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];
int b = y + dy[i];
if(a < 5 && a >= 0 && b < 5 && b >= 0){
curStatus[a][b] ^= 1;
}
}
}
int main(){
int T;
scanf("%d",&T);
while(T--){
char backup[6][6];
for(int i = 0; i < 5; i++){
scanf("%s",backup[i]);
}
int res = -1;
for(int op = 0; op < 32; op++){
int cnt = 0;
memcpy(curStatus, backup, sizeof curStatus);
for(int i = 0; i < 5; i++){
if(op >> i & 1){
turn(0, i);
cnt++;
}
}
//递推一到四行的状态
for(int i = 0; i < 4; i++){
for(int j = 0; j < 5; j++){
if(curStatus[i][j] == '0'){
turn(i + 1, j);
cnt++;
}
}
}
//检查最后一行是否为全为亮
bool success = true;
for(int i = 0; i < 5; i++){
if(curStatus[4][i] == '0'){
success = false;
break;
}
}
if(success && cnt <= 6){
res = cnt;
}
}
printf("%d\n",res);
}
return 0;
}