|
题目描述
第一次写题解，如有解释不清的地方，欢迎留言
基本上“费解的开关”代码差不多，进行了小幅度修改：
1、位运算枚举每一行可能的操作（课上是只枚举一行，这里枚举四行）
2、turn函数是改变其他开关的状态
3、vector数组存改变的开关位置（操作优点像“算法基础课”的有些内容）
简单来讲就是暴力算法
自己写的，还没看讲解视频，代码肯定没那么优雅，还请谅解
C++ 代码
#include
#include
#include //STL
#include //要用sort函数
using namespace std;
typedef pair PII; //对组
const int N = 5;
char g[N][N] , backup[N][N]; //和费解的开关作用一样
vectorway; //开一个对组数组存操作的开关位置
void turn(int x,int y)//按题目要求改变开关状态
{
for(int i = 0 ; i < 4 ; i ++ )//横向改变
{
if ( g[x][i] == '+' )
{
g[x][i] = '-';
continue;
}
else g[x][i] = '+' ;
}
for(int i = 0 ; i < 4 ; i ++ )//纵向改变
{
if( i != x ) 注意：(x,y)坐标只改变一次状态
{
if ( g[i][y] == '+' )
{
g[i][y] = '-' ;
continue;
}
else g[i][y] = '+' ;
}
}
}
int main()
{
for(int i = 0 ; i < 4 ; i ++) cin>>g[i];
int res = 20; //这个20是试案例试出来的
//要先位运算枚举四行开关的操作，1表示操作，0表示不操作
for(int op1 = 0 ; op1 < 16 ; op1 ++)
for(int op2 = 0 ; op2 < 16 ; op2 ++)
for(int op3 = 0 ; op3 < 16 ; op3 ++)
for(int op4 = 0 ; op4 < 16 ; op4 ++)
{
memcpy(backup,g,sizeof g);
int step = 0 ; //记录最小步数
for(int i = 0 ; i < 4 ; i ++)
{
if ( op1 >> i & 1) //每行一个一个判断
{
step ++ ;
turn ( 0 , i ) ;
way.push_back( {0,i} ); //这里先把每个改变的开关位置保存下来，stl内容
}
if ( op2 >> i & 1)
{
step ++ ;
turn ( 1 , i ) ;
way.push_back( {1,i} );
}
if ( op3 >> i & 1)
{
step ++ ;
turn ( 2 , i ) ;
way.push_back( {2,i} );
}
if ( op4 >> i & 1)
{
step ++ ;
turn ( 3 , i ) ;
way.push_back( {3,i} );
}
}
//判断冰箱开没开
bool flag = false ;
for(int i = 0 ; i < 4 ; i ++)
for(int j = 0 ; j < 4 ; j ++)
{
if ( g[i][j] == '+' ) flag = true ;
}
if(!flag)
{
res=min(res,step);
sort(way.begin(),way.end()); //按从上到下（对组第一个数），从左到右排序（对组第二个数）
}
else way.erase(way.end()-step,way.end()); //不能开冰箱则将本次操作存的坐标删除
memcpy(g,backup,sizeof backup);
}
cout |