前排警告:请一定要看清题目!!!
因为把相邻十字看成大十字我调了半个小时!
因为没看到小于6我活生生又调了十多分钟!
题目描述
给一个01矩阵,你可以进行一种操作,使其自己及其上下左右相邻块取反逆转(共5个块)
思路(详细!)
我们可以再开一个01矩阵,对应矩阵中该位置是按还是不按
因为一个位置最多只应该按一下,如果按两下的话跟按0下的效果是一样的
根据这个矩阵,我们可以跟方便处理和计算
先把问题化小,先看看只有一行5个灯泡会怎么样
01010
思路很显然,数据量相当小
就算直接暴力枚举每个开关摁与不摁的情况都只需要2^5(32)种情况
加一行看看:
01010
10101
这样子的话,我们还是偏向于使用暴力枚举
原因是上下只有两行,摁一行的灯会影响另一行,很难有优化策略
于是我们再加一行
01010
10101
01010
看到了吗?路开始走宽了!
首先,我们还是可以用搜索,不过我们有了剪枝策略:
如果搜索到了第三行,第一行还没有被摁成全亮的话,就剪枝
因为无论你怎么按第三行,都不可能对第一行有影响!!!
(因为没看清相邻十字的我再生气一遍)(`⌒´メ)
而根据这个思路,除了搜索,我们还有枚举+递推的方法
也就是枚举第一行的所有摁法(32种)
然后,根据第一行的摁到的结果摁第二行
怎么摁第二行呢?因为只有一二行可以改变一行状态
所以按完二行必须保证一行已经全亮
即:一行里的0往下对应的二行位置必须按,一行里的1往下对应的二行位置一定不能按
所以,对于每一种一行按法,二行的按法是确定的
而按完二行后,可以影响二行的只有三行
所以三行为了保证二行全亮,按法确定
那么如果三行按完之后不全亮呢?
就说明这种一行摁法不正确,枚举下一个
这种思路扩大到5行依旧合用:
01010
01010
10101
11011
00111
总结的算法就是两种:
剪枝搜索(dfs)
枚举+递推
当然还有别的,但是本蒟蒻能力有限
算法1(剪枝搜索) O(n) //每组数据为常数
用一个bool s[25]表示一种状态
枚举每一个节点摁与不摁的状态
时间复杂度
剪枝之后实际复杂度远低于理论
C++ 代码
#include <iostream>
using namespace std;
int n;
bool zt[25];
int ans=26;
int num,sum;
void clik(int cal){
zt[cal]=!zt[cal];
if(cal%5==0){
zt[cal+1]=!zt[cal+1];
}else if(cal%5==4){
zt[cal-1]=!zt[cal-1];
}else{
zt[cal+1]=!zt[cal+1];
zt[cal-1]=!zt[cal-1];
}
if(cal<5){
zt[cal+5]=!zt[cal+5];
}else if(cal>19){
zt[cal-5]=!zt[cal-5];
}else{
zt[cal+5]=!zt[cal+5];
zt[cal-5]=!zt[cal-5];
}
}
void dfs(){
if(zt[0]&&zt[1]&&zt[2]&&zt[3]&&zt[4]&&zt[5]&&zt[6]&&zt[7]&&zt[8]&&zt[9]&&zt[10]&&zt[11]&&zt[12]&&zt[13]&&zt[14]&&zt[15]&&zt[16]&&zt[17]&&zt[18]&&zt[19]&&zt[20]&&zt[21]&&zt[22]&&zt[23]&&zt[24])
ans=min(ans,sum);
if(num>24){
return;
}
if(sum>=ans){
//其实大于六就应该剪枝,没看到T^T,但是还是可以过
return;
}
for(int i=3;i<=5;i++){
if(num>=(i*5)&&!(zt[(i-3)*5+0]&&zt[(i-3)*5+1]&&zt[(i-3)*5+2]&&zt[(i-3)*5+3]&&zt[(i-3)*5+4])){
return;
}
}
num++;
dfs();
num--;
clik(num);
num++;
sum++;
dfs();
num--;
sum--;
clik(num);
return;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
while(n--){
char ch;
for(int i=0;i<25;i++){
cin >> ch;
zt[i]=bool(ch-'0');
}
num=0,sum=0,ans=26;
dfs();
ans=(ans>6 ? -1 : ans);
cout << ans << endl;
}
}
算法2(枚举+递推) O(n) //处理单组为常数级
先搜索(dfs)得到第一行所有按法的结果
这一步可以在上面代码的基础上稍加改动得到
然后枚举每一个结果,舍去不能达到的,在达到的里面取最小的
时间复杂度
O(n),最后跑测评的结果时间是上一种方法的十分之一!!!
C++ 代码
#include <iostream>
#include <cstring>
using namespace std;
int n;
bool tem[32][25];
bool zt[25];
int yu[32];
int ans=26;
int di,ta;
void clik(int cal){
zt[cal]=!zt[cal];
if(cal%5==0){
zt[cal+1]=!zt[cal+1];
}else if(cal%5==4){
zt[cal-1]=!zt[cal-1];
}else{
zt[cal+1]=!zt[cal+1];
zt[cal-1]=!zt[cal-1];
}
if(cal<5){
zt[cal+5]=!zt[cal+5];
}else if(cal>19){
zt[cal-5]=!zt[cal-5];
}else{
zt[cal+5]=!zt[cal+5];
zt[cal-5]=!zt[cal-5];
}
}
void dfs(){
if(di>4){
return;
}
for(int i=0,k=ta;i<k;i++){
memcpy(zt,tem[i],sizeof(zt));
clik(di);
yu[ta]=yu[i]+1;
memcpy(tem[ta++],zt,sizeof(zt));
}
di++;
dfs();
return;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
while(n--){
char ch;
for(int i=0;i<25;i++){
cin >> ch;
tem[0][i]=bool(ch-'0');
}
ta=1,di=0,ans=26;
dfs();
for(int i=0;i<32;i++){
memcpy(zt,tem[i],sizeof(zt));
int rem=yu[i];
for(int j=1;j<5;j++){
for(int w=0;w<5;w++){
if(!zt[5*(j-1)+w]){
clik(5*j+w);
rem++;
}
}
}
if(zt[20]&&zt[21]&&zt[22]&&zt[23]&&zt[24]){
ans=min(ans,rem);
}
}
ans=(ans>6 ? -1 : ans);
cout << ans << endl;
}
}