思路 【类似八数码】
- 位运算(开关
^1
即可) + 递推 - 每一个位置最多只会操作一次。操作两次==不操作,自然就不可能是最优解。
- 递推:第一行是不可以按的,第一行的要按的格子,确定了第二行要按的相应位置。换句话说,只能从下一行去改变上一行的灯的状态。
- 最后一行是不能按的。【因为它的上面行已经全是1了,我们就无法修改最后一行了】
- cnt 和 ans 要写for里面 教训!!!最早写在全局变量,在那调半天都调不出来。。
C++ 代码
#include <bits/stdc++.h>
using namespace std ;
const int N = 7;
char g[N][N];
int m;
void open(int x, int y) {
int dx[5] = {0, -1, 0, 1, 0}, dy[5] = {0, 0, 1, 0, -1};//分别对应 本位 右下左上
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) {//判断是否在5x5内
g[a][b] ^= 1;//异或 同 0 异1
}
}
}
int work() {
//取无穷 并不影响最大值
int ans = 1e8;//cnt 和 ans 要写for里面 教训!!!
for (int k = 0; k < 32; k ++) {//枚举第一行所以按法
int cnt =0;
char tmp[10][10];//储存g
memcpy(tmp,g,sizeof g);//copy g —> tmp
for (int j = 0; j < 5; j ++) { // <<优先级高于 &(只有1&1 == 1)
if ((k >> j) & 1) { //位运算 举例12和2 二进制分别是
cnt ++; // 01100 和 00010
open (0,j); //按第4、3位 按第2位
}
}
//根据第一行 递推前四行
for (int i = 0; i < 4; i ++) {
for (int j = 0; j < 5; j ++) {
if(g[i][j] == '0') {
cnt ++;
open(i + 1, j);
}
}
}
//判断第四行是否全为1
bool is_successful = true;
for(int j = 0; j < 5; j ++) {
if(g[4][j] == '0') {
is_successful = false;
break;
}
}
if(is_successful) {
ans = min(ans,cnt);
}
memcpy(g,tmp,sizeof g);//恢复原状
}
if(ans > 6) {
ans = -1;
}
return ans;
}
int main () {
cin >> m;
while ( m --) {
for (int i = 0; i < 5; i ++) {
cin >> g[i];
}
cout << work() << endl;
}
return 0;
}
如果对您有帮助的话,不烦点个支持~~