---
title: "飞行员兄弟"
created: 2025-11-28
tags:
  - 算法
---

# 飞行员兄弟

## 题目 [飞行员兄弟](https://www.acwing.com/problem/content/118/)

![[image-f36d99e6.png]]

## 思路分析

一个把手改变，会使所在行列的所有把手全部反转

特点：

①在最优解里面每个把手只按一次，按两次没有区别，

②按的顺序无关紧要，最终取决于这个把手按的次数

可以递推出来吗？ 很难

因为前面的题都是通过某种顺序，每一次都是影响一个灯泡，

但是这个题 不能使用前面的办法，因为操作一次会影响好多灯泡

所以想朴素做法

发现这个题的数据范围很小，所以尝试用暴力解决ac

暴力思路：

①16个开关，所有开关的状态数量是2^16

状态数量即最大操作次数2^16（65536）,既然也不大，那就①枚举所有的方案， 然后按照这个方案来操作

②如果可以实现把手全开，证明此方案合法

③然后统计这个方案里面需要操作的把手数量

④在所有能按的开关数量里取一个最小值 输出方案注意:若两种方案步数相同，按字典序（先按横坐标排序，再按纵坐标排序）

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

#define x first

#define y second

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;

        //先备份一下，为什么？因为最终方案要最少的

        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;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[递推数列|递推数列]] 🏠 [[00-刷题理模型]] ➡️ [[凸多边形的划分|凸多边形的划分]]