luogu题解：P10456 The Pilots Brothers' refrigerator【缺少 SPJ】

思路

此题题意酷似 P10449. 费解的开关。
https://www.luogu.com.cn/problem/P10449

不同之处便是状态连锁改变不同,但做法截然不同,此题是一个 \(4\times4\) 的矩阵。

暴力枚举的复杂度是 \(O( 10^7 )\) ,即 \(2^{16} \times 16\times16 = 16777216\) , \(10^7\) 的复杂度可以通过此题。

但费解的开关一题 为 \(5 \times 5\) 的矩阵,所以不可以暴力枚举。

枚举每个把手拉或不拉，每种拉完后的结果用二进制数 \(k\) 来表示（状态压缩）， \(4\times4\) 个把手编号为 \(0\sim15\) ,输出时为 \(（i \div 4+1，i \mod 4+1）\) 。

……具体细节看代码吧。

时间复杂度

\(O( 10^7 )\) ,即 \(2^{16} \times 16\times16 = 16777216\)

代码

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

完结撒花。