acwing 116.飞行员兄弟 (算法竞赛进阶指南 p48 t1 ) 题解

yingxilin / 2023-08-12 / 原文

原题链接

https://www.acwing.com/problem/content/description/118/

题目描述

“飞行员兄弟”这个游戏，需要玩家顺利的打开一个拥有16个把手的冰箱。

已知每个把手可以处于以下两种状态之一：打开或关闭。

只有当所有把手都打开时，冰箱才会打开。

把手可以表示为一个4х4的矩阵，您可以改变任何一个位置[i,j]上把手的状态。

但是，这也会使得第i行和第j列上的所有把手的状态也随着改变。

请你求出打开冰箱所需的切换把手的次数最小值是多少。

输入格式
输入一共包含四行，每行包含四个把手的初始状态。

符号“+”表示把手处于闭合状态，而符号“-”表示把手处于打开状态。

至少一个手柄的初始状态是关闭的。

输出格式
第一行输出一个整数N，表示所需的最小切换把手次数。

接下来N行描述切换顺序，每行输入两个整数，代表被切换状态的把手的行号和列号，数字之间用空格隔开。

数据范围：
1 <= i,j <=4

样例

输入样例

-+--
----
----
-+--

输出样例：

注意：如果存在多种打开冰箱的方式，则按照优先级整体从上到下，同行从左到右打开。

算法

思路

此题题意酷似 acwing 95. 费解的开关 https://www.acwing.com/problem/content/97/

不同之处便是状态连锁改变不同，但做法截然不同，此题是一个4*4的矩阵，
暴力枚举的复杂度是 O( 10^7 ), (2^16 * 16 * 16 = 16,777,216) ,10^7的复杂度可以通过此题。
但费解的开关一题为5 * 5 的矩阵，所以不可以暴力枚举

枚举每个把手拉或不拉，每种拉完后的结果用二进制数k来表示（状态压缩），4*4个把手编号为0~15，输出时为（i/4+1，i%4+1）。

……具体细节看代码吧

时间复杂度

O( 10^7 ) , 2^16 * 16 * 16 = 16,777,216

C++ 代码

#include<iostream>
#include<cstring>
using namespace std;
char c[4][4];
//目的：全部为'-'
int ans=16;//答案
int ansk=(1<<16)-1;//答案状态

void ch(char &c)//拉动单个把手
{
    if(c=='+') c='-';
    else c='+';
}

void trun(int x,int y)//连锁状态的改变
{
    for(int i=0;i<4;i++)
    {
        ch(c[i][y]);
        ch(c[x][i]);
    }
    ch(c[x][y]);
}

void dfs(int u,int res,int k)//u表示当前编号，res表示已经拉动的个数，k表示二进制下的状态（一个16位的二进制数）
{
    if(u>15)//遍历完一遍
    {

        bool is_true=1;

        //判断是否合法
        for(int i=0;i<4;i++)
            for(int j=0;j<4;j++)
                if(c[i][j]=='+')//不合法
                {
                    is_true=0;
                    break;
                }

        if(is_true==1)
        {
            if(res<ans)//更新答案,注意ansk也要更新
            {
                ans=res;
                ansk=k;
            }
        }

        return ;
    }
    int x=u/4,y=u%4;//行为u/4,列为u%4
    trun(x,y);
    res++;
    k+=1<<u;

    dfs(u+1,res,k);//拉动此把手

    trun(x,y);
    res--;
    k-=1<<u;
    //还原现场

    dfs(u+1,res,k);//不拉动次把手
}
void nout()
{
    cout<<ans<<endl;

    for(int i=0;i<16;i++)
    {
        if(ansk>>i&1)//如果第i位为1，表示拉动了
        {
            cout<<i/4+1<<" "<<i%4+1<<endl;
            //注意：因为答案行列的编号从1~4，而我们存的是0~3，所以记得+1
        }
    }

}
int main()
{
    for(int i=0;i<4;i++)    cin>>c[i];//读入

    dfs(0,0,0);//从第0个开始枚举，已经拉动了0次，状态为0（什么都没拉）

    nout();//输出    

    return 0;
}