参考文献
y总视频
题目描述
飞行员兄弟(虽然我不知道这个题目跟这个题有什么关系)
//一个把手改变,会使所在行列的所有把手全部反转
//特点:①在最优解里面每个把手只按一次,按两次没有区别,
//②按的顺序无关紧要,最终取决于这个把手按的次数!!!
//思考这个题可以递推出来吗? 答案是:很难
//可以想一想,前面的题都是通过某种顺序,每一次都是影响一个灯泡,但是这个题
//不能使用前面的办法,因为操作一次会影响好多灯泡。所以想一想朴素做法
//我们发现这个题的数据范围很小,所以尝试用暴力解决ac
//暴力思路:①16个开关,所有开关的状态数量想一想是多少? 答案是2^16!这个我感觉
//我这么笨还是可以想出来的,往后怎么想呢?
//状态数量即最大操作次数2^16(65536),既然也不大,那就①枚举所有的方案,
//然后按照这个方案来操作
//②如果可以实现把手全开,证明此方案合法
//③然后统计这个方案里面需要操作的把手数量
//④在所有能按的开关数量里取一个最小值
//ac
//输出方案注意:若两种方案步数相同,按字典序(先按横坐标排序,再按纵坐标排序)
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<algorithm>
//这个宏定义其实也就最后输出的时候应用了(如果我没猜错的话),但是y总的习惯就是好习惯!
#define x first
#define y second
using namespace std;
typedef pair<int,int> PII;
const int N=5;
char g[N][N],backup[N][N];
//映射函数
int get(int x,int y)
{
return x*4+y;//返回第x行第y列上的数是多少
}
void turn_one(int x,int y)
{
if(g[x][y]=='+') g[x][y]='-';
else g[x][y]='+';
}
void turn_all(int x,int y)
{
for(int i=0;i<4;i++)
{
turn_one(x,i);
turn_one(i,y);
}
turn_one(x,y);
}
int main()
{
for(int i=0;i<4;i++)
for(int j=0;j<4;j++)
cin>>g[i][j];
vector<PII> res;//这是记录方案所需要的结构
//枚举所有的方案
for(int op=0;op<1<<16;op++)
{
vector<PII> temp;//temp里面存的是方案
//先备份一下,为什么?因为这又不是最终方案,我们要把所有方案都试一遍,求最少的
memcpy(backup,g,sizeof g);
//枚举16个位置,进行操作
for(int i=0;i<4;i++)
for(int j=0;j<4;j++)
if(op>>get(i,j)&1) //如果当前位置是1的话--get的作用就是返回二进制数中那一位是第几位,从而判断是否为1
{
temp.push_back({i,j});
//按一下开关
turn_all(i,j);
}
//判断所有灯泡是否全亮
bool has_closed=false;
for(int i=0;i<4;i++)
for(int j=0;j<4;j++)
if(g[i][j]=='+') has_closed=true;
if(has_closed==false)
{
//如果方案为空或者他的操作数大于我们刚存好的新的方案,那么就修改它
if(res.empty()||res.size()>temp.size()) res=temp;
}
//还原回来,供下一个方案操作
memcpy(g,backup,sizeof g);
}
//因为没说无解,所以可以猜想一下一定有解
cout<<res.size()<<endl;
//这里的迭代函数就是一种简便写法,不要误解
//另外原题下标从1开始,所以下面加1了
for(auto op:res) cout<<op.x+1<<" "<<op.y+1<<endl;
return 0;
}
其实我大部分都看懂了,但是没有看懂这个枚举过程。
因为这题跟大多数DFS题一样,每一个位置最终其实要么被操作一次,要么不被操作。(多次操作等效)。所以不妨将操作一次的记为1,不操作的地方记为0。
我们将16个位置,用位来表示就是16个01的组合。
比如
0000 0000 0000 0000
就表示对所有的都不操作,1111 0000 0000 0000 0000
表示对第一行全部进行操作。 反正我们最终的解,也就是经过多次操作得到的结果也可以用这么一串数字表示。再比如题目中的示例,最终的解为
那么这整个过程的最终操作结果就可以用
1011 0000 0000 1011
表示。所以最外层for循环,就是遍历这么一个过程:从
0000 0000 0000 0000
到1111 1111 1111 1111
,也就是0 到
1<<16`(用位运算表示了而已)。相当于枚举了所有可能的解。
二进制枚举 :把每种情况当作一组二进制序列, (例如0000 0000 0000 0101就是对1和3位置(用get求) 的灯泡反转)
所以最外层循环遍历所有情况 ,内层for(i:4)for(j:4)是对此情况下的为1的位置进行反转处理,(op>>get(i,j)&1)就是的到二进制序列中的第get(i,j)位,如果为1,就是对(i,j)反转
大佬 想问一下 if(op>>get(i,j)&1) 这个判断如何理解
枚举op 0~(1<<16)-1 并判断在2进制情况下枚举每一位上的数字是否为1
谢谢 已经明白啦 其实就是枚举每个方案 是用二进制构成的方案数
判断get(i, j)位是不是1(要不要按开关)
为什么是1就要按开关嘞
这个是自己定义的,你把0当作按的情况也没有问题,只要能用1和0把所有按与不按的情况都表示出来即可
无论按1还是按0,你最终都会把所有情况枚举一遍的,所以是相同的
if(op>>get(i,j)&0)为甚么不行请问
真的牛逼,看视频没懂看你的题解懂了!tql
#include[HTML_REMOVED]
#include[HTML_REMOVED]
#include[HTML_REMOVED]
#include[HTML_REMOVED]
#include[HTML_REMOVED]
using namespace std;
typedef pair[HTML_REMOVED] PII;
const int N=6;
char st[N][N],backrup[N][N];
void turn_one(int x,int y){
if(st[x][y]==’+’) st[x][y]=’-‘;
else
st[x][y]=’+’;
}
void turn_all(int x,int y){
for(int i=0;i<4;i){
turn_one(x,i);
turn_one(i,y);
}
turn_one(x,y);
}
int main(){
vector[HTML_REMOVED]result;
for(int i=0;i<4;i) cin>>st[i];
}
差不多为什么我这有错误
清晰:)
你是真的优秀,竟然可以用《费解的开关》这道题的方法
感谢大佬分享思路hh
妙啊,这个思路我是怎么都不可能想出来的orz
输入换成 scanf(“%c”,&g[i][j]); 为什么就错了
去掉地址符
去掉地址符也是错的,为什么呢
输入单个字符 %c和&都要有
输入字符串 %s要有 &不需要
单句语法肯定没有问题 脱离代码谈错误就是耍流氓
会不会%c把换行符读进去了 ,是的话加个getchar()
if(op>>get(i,j)&0)为甚么不行请问
for (auto op : res)
这个可以换别的写法吗,不是特别理解
if(op >> get(i, j) ^ 1) 写成异或为什么不对呢
好强,我想到了暴力枚举,但是没想到枚举的方式
为啥y总每次读入都只读入g[i],而不是g[i][j]
每次读入的都是一整行
这个是字符数组把,好像能这样
请教下大佬,只接触过c没接触过cpp请问vector[HTML_REMOVED]res中的pII是一个新的数组,res也是吗?res代表的是记录方案的所需结构具体指的是什么?
刚才又看了下我的表述有点错误,我的意思是vector res放在那个位置不一直是空的吗为什么后面要res.size()>temp.size()一下
temp相当于一个临时的vector,为了记录能使所有开关全部打开的步数,res是最终结果,要的是最小的那个步数,当满足res.size()>temp.size()时,说明此时这个临时vector的方案所需的步数更少,就把更小的步数放到res中,即res=temp
想问一下为什么用
来取代turn_one 和turn_all函数就是错的呢(费解的开关里的方法)
哦哦哦我明白了,应该考虑13个点才可以
题目名说的大概是飞机上上上下下的扳钮有一堆/xk
for(int it=0;it<res.size();it++) cout<<res[it].x+1<<” “<<res[it].y+1<<endl;为什么最后用这个输出不出来
这是vector
还是没懂 if(op>>get(i,j)&1) 哪位大佬能给举个例子😭
懂了 用这种来枚举开关是开还是关
这个枚举可不可以看成说就是用二进制数来存储整个数组。。
if(op>>get(i,j)&0)为甚么不行请问
if(op>>get(i,j)&1) 这到底是啥意思呢 ?
op向左移get(i,j)次,get(i,j)就是第i行第j列代表的数字,和1取和代表判断op的第get(i,j)位是不是1
if(op>>get(i,j)&0)为甚么不行请问