AcWing 116. 飞行员兄弟（超详细注释）因为看了三遍

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 116. 飞行员兄弟（超详细注释）因为看了三遍原题链接简单

作者：

山雾 , 2022-01-07 14:17:41 , 所有人可见 , 阅读 10251

94

46

参考文献

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;
}

74 评论

Codemon 2023-03-22 20:17

其实我大部分都看懂了，但是没有看懂这个枚举过程。

因为这题跟大多数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`（用位运算表示了而已）。

相当于枚举了所有可能的解。

尘客_2 2023-05-17 12:26

二进制枚举 :把每种情况当作一组二进制序列, (例如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)反转

Pinguier 2022-12-21 00:02

大佬想问一下 if(op>>get(i,j)&1) 这个判断如何理解

华工苏神 2023-01-16 14:28

枚举op 0~（1<<16）-1 并判断在2进制情况下枚举每一位上的数字是否为1

Pinguier 2023-01-16 19:14 回复了华工苏神的评论

谢谢已经明白啦其实就是枚举每个方案是用二进制构成的方案数

Kessie龙潜 2023-07-20 11:46

判断get(i, j)位是不是1（要不要按开关）

星卅. 2023-12-20 14:04 回复了 Pinguier 的评论

为什么是1就要按开关嘞

你爹来咯 10个月前回复了星卅. 的评论

这个是自己定义的，你把0当作按的情况也没有问题，只要能用1和0把所有按与不按的情况都表示出来即可

Rebirth_83 9个月前回复了星卅. 的评论

无论按1还是按0，你最终都会把所有情况枚举一遍的，所以是相同的

acwing_8880 7个月前回复了 Rebirth_83 的评论

if(op>>get(i,j)&0)为甚么不行请问

p_nullptr_j 11个月前

真的牛逼，看视频没懂看你的题解懂了！tql

一一呀 2023-11-15 21:32

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 5;
char q[N][N], backup[N][N];

//翻转一行或一列
void turn_one(int x, int y)
{
    if (q[x][y] == '+') q[x][y] = '-';
    else q[x][y] = '+';
}

void turn_all(int x, int y)
{
    for (int i = 0; i < 4; i++)
    {
        turn_one(x, i);
        turn_one(i, y);
    }
    //因为有个点翻转了2次变回原来的状态了，需要再翻转一次
    turn_one(x, y);
}

int main()
{
    vector<pair<int, int>> res;
    for (int i = 0; i < 4; i++) cin >> q[i];

    for (int op = 0; op < 1 << 16; op++)
    {
        vector<pair<int, int>> temp;
        memcpy(backup, q, sizeof q);

        //枚举16个开关的所有情况
        for (int i = 0; i < 16; i++)
        {
            //在方式相同（即op里1的个数相同）的情况下，按照优先级整体从上到下，同行从左到右打开
            //即 1 应该在前面（高位），如 11001 和 00111 选前者，虽然这道题实际上有唯一解……
            // >> 右移是从右到左的，所以应该 op>>(15-i)&1 从高位开始
            if (op >> (15 - i) & 1)
            {
                temp.push_back({i / 4, i % 4}); //将0~15转换为行和列
                turn_all(i / 4, i % 4);
            }
        }

        bool clo = false; //是否全部都打开了
        for (int i = 0; i < 4; i++)
        {
            for (int j = 0; j < 4; j++)
            {
                if (q[i][j] == '+')
                {
                    clo = true;
                    break;
                }
            }
        }
        if (!clo)
        {
            if (res.empty() || res.size() > temp.size()) res = temp;
        }
        memcpy(q, backup, sizeof backup);
    }
    cout << res.size() << endl;
    for (auto op : res) cout << op.first + 1 << ' ' << op.second + 1 << endl;

    return 0;
}

麻雀001 6个月前

#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];

for(int i=0;i<1<<16;i++){
    vector<PII>temp;
    memcpy(backrup,st,sizeof st);
    for(int j=0;j<16;j++){
        if(i>>j&1){
            temp.push_back({i/4,i%4});
            turn_all(i/4,i%4);
        }
    }
    bool close=false;
    for(int i=0;i<4;i++){
        for(int j=0;j<4;j++){
            if(st[i][j]=='+') close=true;  
        }
    }
    if(!close){
        if(result.empty()||result.size()>temp.size()) result=temp;
    }
    memcpy(st,backrup,sizeof st);
}
if(result.size()>6)  cout<<-1<<endl;
else {
    cout<<result.size()<<endl;
    for(auto r:result)  
        cout<<r.first+1<<" "<<r.second+1<<endl;
}
return 0;

}
差不多为什么我这有错误

plutooo89 3个月前

清晰：）

人间最失意 2023-10-30 18:56

你是真的优秀，竟然可以用《费解的开关》这道题的方法

scskd2 2022-11-18 11:16

感谢大佬分享思路hh

冒泡了 5个月前

#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

typedef pair<int, int> PII;
const int N = 4;

vector<PII> res;
char arr[N][N], cpy[N][N];

void turn(int x, int y)
{
    for (int i = 0; i < N; i++)
        cpy[x][i] = cpy[x][i] == '+' ? '-' : '+';
    for (int i = 0; i < N; i++)
        cpy[i][y] = cpy[i][y] == '+' ? '-' : '+';
    cpy[x][y] = cpy[x][y] == '+' ? '-' : '+';
}

int main()
{
    for (int i = 0; i < N; i++)
            cin >> arr[i];

    for (int op = 0; op < 1 << 16 ; op++)
    {
        memcpy(cpy, arr, sizeof(arr));
        vector<PII> t;
        for (int i = 0; i < N * N; i++)
            if (op >> i & 1)
            {
                turn(i / N, i % N);
                t.push_back({i / N, i % N});
            }

        bool flag = true;
        for (int i = 0; i < N * N; i++)
            if (cpy[i / N][i % N] == '+')
            {
                flag = false;
                break;
            }

        if (flag)
        {
            if (res.empty() || t.size() < res.size()) res = t;
        }
    }

    cout << res.size() << endl;
    for (int i = 0; i < res.size(); i++)
    {
        cout << res[i].first + 1 << " " << res[i].second + 1<< endl;
    }

    return 0;
}

没关系啦 2023-04-02 20:02

妙啊，这个思路我是怎么都不可能想出来的orz

llp 2022-03-25 22:18

输入换成 scanf(“%c”,&g[i][j]); 为什么就错了

熊全明 2022-03-26 11:19

去掉地址符

z.m 2023-03-21 18:05 回复了熊全明的评论

去掉地址符也是错的，为什么呢

Acxxxqq 2023-03-29 09:06 回复了 z.m 的评论

输入单个字符 %c和&都要有
输入字符串 %s要有 &不需要
单句语法肯定没有问题脱离代码谈错误就是耍流氓

尘客_2 2023-05-17 10:19 回复了 z.m 的评论

会不会%c把换行符读进去了 ,是的话加个getchar()

661想果艺 2个月前

#include[HTML_REMOVED]
#include[HTML_REMOVED]
#include[HTML_REMOVED]
using namespace std;
#define x first
#define y second
char fz[5][5];
typedef pair[HTML_REMOVED]PII;
char g[5][5];
int get(int x,int y){
return x=x*4+y;
}

void turn(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(x,i);
turn(i,y);
}
turn(x,y);
}
int main(){

for(int i=0;i<4;i++){
    cin>>g[i];
}


vector<PII>res;

for(int op=0;op<1<<16;op++){


    vector<PII>temp;
    memcpy(fz,g,sizeof g);



    for(int i=0;i<4;i++){
        for(int j=0;j<4;j++){
            if(op>>get(i,j)%1){
                temp.push_back({i,j});
                turn_all(i,j);
            }
        }
    }


    bool st=true;
    for(int i=0;i<4;i++){
        for(int j=0;j<4;j++){
            if(g[i][j]=='+')
            st=false;
        }
    }


    if(st){
        if(res.empty()||res.size()>temp.size())res=temp;
    }
    memcpy(g,fz,sizeof g);
}




cout<<res.size()<<endl;
 for(auto op:res){
        cout<<op.x+1<<" "<<op.y+1<<endl;
    }




return 0;

}
按照y总思路写的，不知道哪里写错了

acwing_8880 7个月前

if(op>>get(i,j)&0)为甚么不行请问

佑佑变强日记 8个月前

for (auto op : res)
这个可以换别的写法吗，不是特别理解

ricardo_8 9个月前

if(op >> get(i, j) ^ 1) 写成异或为什么不对呢

万a 10个月前

好强，我想到了暴力枚举，但是没想到枚举的方式

用户名到底存不存在 10个月前

为啥y总每次读入都只读入g[i]，而不是g[i][j]

踢足球的程序员 10个月前

每次读入的都是一整行

阿哈的艰难学习 9个月前

这个是字符数组把，好像能这样

小笔摘纸 10个月前

请教下大佬，只接触过c没接触过cpp请问vector[HTML_REMOVED]res中的pII是一个新的数组，res也是吗？res代表的是记录方案的所需结构具体指的是什么？

小笔摘纸 10个月前

刚才又看了下我的表述有点错误，我的意思是vector res放在那个位置不一直是空的吗为什么后面要res.size()>temp.size()一下

你爹来咯 10个月前回复了小笔摘纸的评论

temp相当于一个临时的vector，为了记录能使所有开关全部打开的步数，res是最终结果，要的是最小的那个步数，当满足res.size()>temp.size()时，说明此时这个临时vector的方案所需的步数更少，就把更小的步数放到res中，即res=temp

bukki 11个月前

想问一下为什么用

int dx[7]={-1,0,0,0,0,1,2};
int dy[7]={0,-1,0,1,2,0,0};

void turn(int x,int y){
for(int i=0;i<7;i++){
int a=x+dx[i];
int b=y+dy[i];
if(a<0||a>3||b<0||b>3) continue;
if(g[a][b]==’-‘) g[a][b]=’+’;
else g[a][b]=’-‘;
}

}

来取代turn_one 和turn_all函数就是错的呢（费解的开关里的方法）