一道非常好的递推练习题。
我们考虑每次枚举第一行的操作，由上一行的状态递推出下一行的状态，最后判断最后一行是否全部为 \(1\) 即可。
实现代码时要注意一些细节问题。
#include <bits/stdc++.h>
#define DEBUG fprintf(stderr, "Passing [%s] line %d\n", __FUNCTION__, __LINE__)
#define itn int
#define gI gi
using namespace std;
typedef long long LL;
typedef pair <int, int> PII;
typedef pair <int, PII> PIII;
inline int gi()
{
int f = 1, x = 0; char c = getchar();
while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return f * x;
}
inline LL gl()
{
LL f = 1, x = 0; char c = getchar();
while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return f * x;
}
const int dx[] = {0, -1, 0, 1, 0}, dy[] = {0, 0, 1, 0, -1};
//定义常量数组表示当前要翻转的灯及它上下左右的位置
int n, m;
char g[7][7];
inline void get(int x, int y) //摁下第 x 行 y 列的灯
{
for (int i = 0; i < 5; i+=1) //将它本身及四周的灯翻转状态
{
int xx = x + dx[i], yy = y + dy[i];
if (xx >= 0 && xx <= 4 && yy >= 0 && yy <= 4) //在界内
{
//进行翻转
if (g[xx][yy] == '1') g[xx][yy] = '0';
else g[xx][yy] = '1';
}
}
}
inline int getans() //求答案
{
int ans = 66666666;
for (int k = 0; k < (1 << 5); k+=1) //枚举每一种第一行的操作状态
{
int sum = 0; //操作的总数
char bf[7][7];
memcpy(bf, g, sizeof g); //先将初始状态备份
for (int j = 0; j < 5; j+=1)
{
if (k >> j & 1) //如果第 j 号灯需要翻转
{
++sum; //操作一次
get(0, j); //将第 j 号灯翻转
}
}
for (int i = 0; i < 4; i+=1) //递推出下一行的状态
{
for (int j = 0; j < 5; j+=1) //枚举第 i 行的每一盏灯
{
if (g[i][j] == '0') //如果这个灯需要被翻转
{
++sum;
get(i + 1, j); //将它下一排的灯翻转
}
}
}
bool ok = true;
for (int j = 0; j < 5; j+=1)
{
if (g[4][j] == '0') {ok = false; break;} //没有达到目标状态
}
if (ok) ans = min(ans, sum); //记录最少步数
memcpy(g, bf, sizeof g); //还原备份
}
if (ans > 6) return -1; //不能在 6 步以内达到目标状态
return ans; //返回答案
}
int main()
{
//freopen(".in", "r", stdin);
//freopen(".out", "w", stdout);
int t = gi(); //多组数据输入数据总数
while (t--)
{
for (int i = 0; i < 5; i+=1) scanf("%s", g[i]); //输入每一行的状态
printf("%d\n", getans()); //输出答案
}
return 0;
}