暴力枚举点 TLE
/*
改变不超过6个点,使图中所有数变为 1
25个点,任意选取 <=6 个点改变状态
每个点,只有两个状态:改变,不改变
边界条件:
25个点全部选取完毕
剪枝条件:
当前改变点数量>6
总共R行C列( 0行0列是第0个点 )
一维索引 -> 二维坐标:u -> ( u/C , u%C )
二维打一维:(r,c) ->r*C+c
*/
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=10;
int g[N][N];
int res;
// 检查是否全是1
bool check(){
for(int i=0; i<5; i++)
for(int j=0; j<5; j++)
if(!g[i][j]) return false;
return true;
}
// 改变状态
int dxy[4][2]={{1,0}, {-1,0}, {0,-1}, {0,1}};
void change(int u){
int x=u/5, y=u%5;
for(int i=0; i<4; i++){
int nx=x+dxy[i][0];
int ny=y+dxy[i][1];
if(nx<0||ny<0) continue; // 越界
g[nx][ny]=g[nx][ny]^1;
}
g[x][y]=g[x][y]^1;
}
// 当前位置 操作次数
void dfs(int u, int w){
// 剪枝情况
if(w>6) return ;
// 边界情况
if(u>24){
if(check() && w<=6)
res=min(res, w);
return ;
}
// 当前位置拥有两种状态选择
// 不改变
dfs(u+1, w);
// 改变
change(u);
dfs(u+1, w+1);
change(u); // 恢复现场
}
int main(){
int n;
cin>>n;
while(n--){
for(int i=0; i<5; i++)
for(int j=0; j<5; j++)
scanf("%1d", &g[i][j]);
res=79;
dfs(0, 0);
if(res==79) res=-1;
printf("%d\n", res);
}
return 0;
}
优化
/*
改变不超过6个点,使图中所有数变为 1
从点出发不行
但若我们一排一排考虑
容易发现,(x, y)点仅仅被(x+1, y)影响
x 行想要亮,x+1行必定改变
而第一行的点击状态则全部枚举出来
每个点两个状态 改变 不改变
边界条件:到第六个点了
在第一排状态枚举完后,需要备份枚举完后的地图状态
因为回溯是从此地图回溯,后面的操作会改变地图,而导致错误
接着我们只需要从第二行开始检查上一行
若上一行有未亮,则改变,看能否在6次内全亮
*/
#include <iostream>
#include <algorithm>
using namespace std;
const int N=10;
int g[N][N];
int backup[N][N];
int res;
// 更新备份
void bf(){
for(int i=0; i<5; i++)
for(int j=0; j<5; j++)
backup[i][j]=g[i][j];
}
// 恢复备份
void rbf(){
for(int i=0; i<5; i++)
for(int j=0; j<5; j++)
g[i][j]=backup[i][j];
}
// 检查只用检查最后一行
bool check(){
for(int i=0; i<5; i++)
if(!g[4][i]) return false;
return true;
}
// 改变状态
int dxy[4][2]={{1,0}, {-1,0}, {0,-1}, {0,1}};
void change(int x, int y){
for(int i=0; i<4; i++){
int nx=x+dxy[i][0];
int ny=y+dxy[i][1];
if(nx<0||ny<0) continue; // 越界
g[nx][ny]=g[nx][ny]^1;
}
g[x][y]=g[x][y]^1;
}
// 第一排的点 当前改变次数
void dfs(int u, int w){
// 到达边界,第一层枚举完毕
if(u>4){
// 保存当前地图
bf();
// 推导剩下四层
for(int i=1; i<5 && w<=6; i++)
for(int j=0; j<5; j++)
if(!g[i-1][j])
change(i, j),w++;
if(check() && w<=6) res=min(res, w);
// 恢复地图
rbf();
return ;
}
// 改变
change(0,u);
dfs(u+1, w+1);
change(0,u); // 恢复现场
// 不改变
dfs(u+1, w);
}
int main(){
int n;
cin>>n;
while(n--){
for(int i=0; i<5; i++)
for(int j=0; j<5; j++){
scanf("%1d", &g[i][j]);
backup[i][j]=g[i][j];
}
res=79;
dfs(0, 0);
if(res==79) res=-1;
printf("%d\n", res);
}
return 0;
}