题目中还有一个坑点,导致WA了一次,仔细看了答案后发现AC的正确结果中包括6,而题目中描述的是6步以内,特地上Google了一下,有如下解释:
《民法典》附则 第一千二百五十九条 民法所称的“以上”、“以下”、“以内”、“届满”,包括本数;所称的“不满”、“超过”、“以外”,不包括本数。
#include<iostream>
#include<cstring>
using namespace std;
char a[10][10];
char temp[10][10];
void turn(int x,int y){//置换开关状态
for(int i = x-1; i <= x+1; ++i){//上中下
temp[i][y] ^= 1;
}
for(int j = y-1; j <= y+1; ++j){//左中右
temp[x][j] ^= 1;
}
//因为两次的for对temp[x][y]进行了两次操作,即多操作了一次
temp[x][y] ^=1;
}
int main(){
int n;
cin >> n;
while(n--){
int min_res = 100000000;
for(int i = 1; i <= 5; ++i){
for(int j = 1; j <= 5; ++j){
cin >> a[i][j];
}
}
int max_i = (1<<5);
for(int i = 0; i < max_i; ++i){//第一行的5个开关共可以组成2^n == 1>>2 种状态,对其中的每种状态逐一的进行枚举
//同时需要把“对第一行哪些开关的切换的全部次数”计入本次总操作的操作次数中
//所以需要把 i 对应的二进制数取出并统计该二进制数中 数字1 的个数 并计入本次的res中
//对接下来的几次不同状态的不同操作次数取一个最小值,即为最优解(最小操作次数)
int res = 0;
memcpy(temp,a,sizeof(a));//将原数组复制到temp数组中进行枚举每种 第一行不同的状态对应不同的操作试验
//printf("第%d次:\n",i);
//print();
for(int index = 0; index < 5; ++index){//先对第一排的开关作操作
if((i >> index) & 1){//需要对第[1][index]开关进行置换操作 (i>>index &1)用于判断 第一排5个位置上 _ _ _ _ _的哪个位置的值为1,为1 的就需要进行置换操作
++res;//本次的操作数加一 第一行的操作
turn(1,5-index);
//print();
}
}
for(int j = 2; j <= 5; ++j){//根据确定的第一行的状态来对第2~5行进行确定的操作
for(int k = 1; k <= 5; ++k){
if(temp[j-1][k] == '0'){//第[j-1][k]个开关是关闭状态
//需要在下一行:第j行进行打开操作,同时对应的上下左右四个开关也需要切换状态
turn(j,k);
//print();
++res;//本次的操作数加一 2~5行的操作
}
}
}
int flag = 1;
for(int k = 1; k <= 5; ++k){//不用检测整个数组,只需检测二维数组的最后一行就可以
if(temp[5][k] == '0'){
flag = 0;
break;
}
}
if(flag){//全打开了
min_res = min(res,min_res);
}
}
if(min_res <= 6){
cout << min_res <<endl;
}
else{
cout << "-1" <<endl;
}
}
return 0;
}
民法通则已经废止了,现在叫民法典
收到,已经纠正