AcWing
  • 首页
  • 课程
  • 题库
  • 更多
    • 竞赛
    • 题解
    • 分享
    • 问答
    • 应用
    • 校园
  • 关闭
    历史记录
    清除记录
    猜你想搜
    AcWing热点
  • App
  • 登录/注册

AcWing 95. 费解的开关    原题链接    中等

作者: 作者的头像   秦淮岸灯火阑珊 ,  2019-01-18 21:38:10 ,  所有人可见 ,  阅读 15954


98


27

题目描述

你玩过“拉灯”游戏吗?25盏灯排成一个5x5的方形。每一个灯都有一个开关,游戏者可以改变它的状态。每一步,游戏者可以改变某一个灯的状态。游戏者改变一个灯的状态会产生连锁反应:和这个灯上下左右相邻的灯也要相应地改变其状态。

我们用数字“1”表示一盏开着的灯,用数字“0”表示关着的灯。下面这种状态

10111
01101
10111
10000
11011
在改变了最左上角的灯的状态后将变成:

01111
11101
10111
10000
11011
再改变它正中间的灯后状态将变成:

01111
11001
11001
10100
11011
给定一些游戏的初始状态,编写程序判断游戏者是否可能在6步以内使所有的灯都变亮。

输入格式
第一行输入正整数n,代表数据中共有n个待解决的游戏初始状态。

以下若干行数据分为n组,每组数据有5行,每行5个字符。每组数据描述了一个游戏的初始状态。各组数据间用一个空行分隔。

输出格式
一共输出n行数据,每行有一个小于等于6的整数,它表示对于输入数据中对应的游戏状态最少需要几步才能使所有灯变亮。

对于某一个游戏初始状态,若6步以内无法使所有灯变亮,则输出“-1”。

数据范围
0<n≤500
输入样例:
3
00111
01011
10001
11010
11100

11101
11101
11110
11111
11111

01111
11111
11111
11111
11111
输出样例:

3
2
-1

正解

大致解题思路:这道题目首先看一眼,我们就可以知道必然与位运算有着密切的关系,因为出现了0和1,这是一个重要的发现,接着我们在仔细分析题意,我们知道如果纯暴力枚举的话,必然是会超时的,那么如何优化呢?因此我们需要从题目中找出非常有用的性质来优化,这是一个大致的思路方向

  1. 每一个位置顶多只会操作一次。因为如果操作两次的话,相当于不操作,必然是不满足最优解。

  2. 在一套方案中,操作的顺序无关紧要,这一个略加思索便可得知

  3. 最重要的性质,如果我们确定了第I行的操作方案的话,那么后面的行数都可以依此递推,下面给出一个详细的解答。

11011
10110
01111
11111
比如说这个例子,如果我们确定了第1行,那么第二行所有的0(坐标:a[i][j])
都只能是第三行a[i+1][j]来修改了,因为如果你第二行修改的话,那么第一行将会打乱,下面每一行依此类推。

所以说,我们只需要得出第一行的顺序,后面的顺序都可以顺序推出

C++ 代码

#include <bits/stdc++.h>
using namespace std;
int n,m,i,j,k,a[7][7],ans1=1e6,b[7][7];//7,7是因为怕在最后一排溢出
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        getchar();
        for (i=1;i<=5;i++)
        {
            for (j=1;j<=5;j++)
            {
                char ch=getchar();
                b[i][j]=ch-'0';
            }
            getchar();
        }
        for (i=0;i<=(1<<5);i++)
        {
            for (j=1;j<=5;j++)
            {
                for (k=1;k<=5;k++)
                    a[j][k]=b[j][k];
            }
            int ans=0;
            for (j=1;j<=5;j++)
                if (i>>(j-1) & 1)
                {
                    ans++;
                    a[1][j-1]^=1;
                    a[1][j+1]^=1;
                    a[1][j]^=1;
                    a[2][j]^=1;
                }
            for (j=1;j<=4;j++)//切记是1~4,而不是2~5,因为我们是控制i+1行,而不是控制第i行
                for (k=5;k>=1;k--)
                    if (!a[j][k])
                    {
                        ans++;
                        a[j][k]^=1;//上面
                        a[j+2][k]^=1;//下面
                        a[j+1][k]^=1;//本身
                        a[j+1][k+1]^=1;//右面
                        a[j+1][k-1]^=1;//左面
                    }
            //cout<<ans<<endl;
            bool ok=true;
            for (j=1;j<=5;j++)
                for (k=1;k<=5;k++)
                    if (!a[j][k])
                        ok=false;
            if (ok)
                ans1=min(ans1,ans);//,cout<<ans<<endl;
        }
        if (ans1>6)
            cout<<-1;
        else
            cout<<ans1;
        ans1=1e7;
        puts("");
    }
    return 0;
}

解法二

运用模块化编程

#include <bits/stdc++.h>
using namespace std;
int a[7][7],b[7][7],n,answer;
int init()
{
    getchar();
    for (int i=1;i<=5;i++)
    {
        for (int j=1;j<=5;j++)
        {
            char ch=getchar();
            a[i][j]=ch-'0';
        }
        getchar();
    }
}
int handle(int x,int y)
{
    b[x][y]^=1;
    b[x-1][y]^=1;
    b[x][y+1]^=1;
    b[x][y-1]^=1;
    b[x+1][y]^=1;
}
bool judge(void)
{
    for (int i=1;i<=5;i++)
        for (int j=1;j<=5;j++)
            if(!b[i][j])
                return false;
    return true;
}
int work(void)
{
    answer=1e7;
    for (int i=1;i<=(1<<5);i++)
    {
        int ans=0;
        memcpy(b,a,sizeof(a));
        for (int j=1;j<=5;j++) 
            if (i>>(j-1) & 1)
            {
                handle(1,j);
                ans++;
            }
        for (int j=1;j<=4;j++)
            for (int k=1;k<=5;k++)
                if (!b[j][k])
                {
                    ans++;
                    handle(j+1,k);
                }
        if (judge())
            answer=min(ans,answer);
    }
    return answer;
}
int main()
{
    cin>>n;
    while(n--)
    {
        init();
        if (work()<=6)
            cout<<answer;
        else
            cout<<"-1";
        puts("");    
    }
    return 0;
}

64 评论


用户头像
以依为终   2019-05-09 11:16      2    踩      回复

哦我懂啦!第一行枚举的i的第j位如果是1,是指第一行的这一位应该被切换状态(开灯或关灯),而和其初始状态无关

用户头像
秦淮岸灯火阑珊   2019-05-09 18:59      1    踩      回复

是的.

用户头像
以依为终   2019-05-10 19:32    回复了 秦淮岸灯火阑珊 的评论         踩      回复

谢谢大佬~

用户头像
秦淮岸灯火阑珊   2019-05-10 20:33    回复了 以依为终 的评论         踩      回复

不谢( ̄_, ̄ )


用户头像
烦恼都丢掉   2023-10-10 19:01         踩      回复

for (i=0;i<=(1<<5);i)
{
for (j=1;j<=5;j
)
{
for (k=1;k<=5;k)
a[j][k]=b[j][k];
}
int ans=0;
for (j=1;j<=5;j
)
if (i>>(j-1) & 1)
{
ans;
a[1][j-1]^=1;
a[1][j+1]^=1;
a[1][j]^=1;
a[2][j]^=1;
}
for (j=1;j<=4;j
)//切记是1~4,而不是2~5,因为我们是控制i+1行,而不是控制第i行
for (k=5;k>=1;k–)
if (!a[j][k])
{
ans;
a[j][k]^=1;//上面
a[j+2][k]^=1;//下面
a[j+1][k]^=1;//本身
a[j+1][k+1]^=1;//右面
a[j+1][k-1]^=1;//左面
}
秦淮岸灯火阑珊,你好!C
代码中if(i>>(j-1)&1)起了什么作用?


用户头像
烦恼都丢掉   2023-10-10 18:45         踩      回复

大佬,你好!C++代码中,
if (ans1>6)
cout<<-1;
else
cout<<ans1;
ans1=1e7;
puts(“”);

作为全局变量ans1已经赋值为1e6;还需要赋值1e7吗?


用户头像
古河渚   2023-09-19 15:44         踩      回复

bang!


用户头像
山河相间灿若星河   2022-08-04 15:32         踩      回复

Orz
Orz
Orz
重要的事情说三遍

用户头像
炽热小老弟   2022-12-18 20:34         踩      回复

这个是什么意思

用户头像
yuki0vo   2023-02-14 22:31    回复了 炽热小老弟 的评论         踩      回复

给大佬跪着磕头orz不觉得很形象吗

用户头像
tz201   2024-07-07 14:53    回复了 yuki0vo 的评论         踩      回复

“象形文字”


用户头像
六七   2021-11-02 11:04         踩      回复

bfs怎么解决


用户头像
空银子   2021-10-25 14:57         踩      回复

for (int i=1;i<=(1<<5);i++) 其实枚举到(1<<5)-1就行了
最后判断是否为0,也只需要判断最后一行,因为上面的程序保证了前四行的数都为1

用户头像
山河相间灿若星河   2022-08-04 15:31         踩      回复

i只有从0开始才能允许枚举到(1<<5)-1


用户头像
三岛柚叶   2021-05-28 13:39         踩      回复

Orz


用户头像
寒江   2020-12-07 00:57         踩      回复

为啥第一行要按1 << 5 次 第一行不是题目给你给好了 0 和 1嘛 这个地方一直不懂

用户头像
泠鸢yousa   2021-01-18 21:17      4    踩      回复

是这样的
自第二行开始向下的op确实会依赖于上层的状态
但是第一层并非直接跳过 直接看第二层的 对第一层不同的操作 第一层会产生不同的状态
因而后序的操作次数会因为 第一层不同操作产生的不同状态而改变
所以最优解是通过枚举第一层所有操作得出来的
可以理解一下 枚举的思想
希望能对你有所帮助

用户头像
寒江   2021-01-18 21:25    回复了 泠鸢yousa 的评论         踩      回复

好滴 明白了 太棒了 !!! 谢谢大佬


用户头像
fafafa   2020-08-20 21:24         踩      回复

Orz


用户头像
xhQYm   2020-03-04 10:27         踩      回复

$QwQ$ STORZ

用户头像
xhQYm   2020-03-04 10:28         踩      回复

大佬666


用户头像
阿基米多多   2019-12-28 15:15         踩      回复

1.每一个位置顶多只会操作一次。因为如果操作两次的话,相当于不操作,必然是不满足最优解。
2.在一套方案中,操作的顺序无关紧要,这一个略加思索便可得知
怎么证明这两个结论是正确的,能具体给出证明过程吗?

用户头像
Mr.Edge   2020-06-30 23:35      2    踩      回复

把取反的过程记作!,假如当前位置为p,结论1:!(......)!p = (......)!!p = (......)p,(......)就是中间的多次取反操作,结论2:对于当前位置p,假设有两个操作会对p取反,那么就是!!p,第一个!和第二个!明显是等价的,都是取反


用户头像
M狼   2019-11-09 11:52         踩      回复

厉害!

用户头像
M狼   2019-11-09 11:52         踩      回复

很清晰

用户头像
秦淮岸灯火阑珊   2019-11-09 17:13    回复了 M狼 的评论         踩      回复

STO


用户头像
lqhsr   2019-10-24 22:09         踩      回复

%%%楼主


用户头像
Frank2008_2   2019-10-05 17:10         踩      回复

666666

用户头像
秦淮岸灯火阑珊   2019-10-05 19:17         踩      回复

QwQ


用户头像
lesileqin   2019-09-23 20:53         踩      回复

感谢巨佬

用户头像
秦淮岸灯火阑珊   2019-09-24 19:25      1    踩      回复

%%%


用户头像
fantastic   2019-08-04 13:10         踩      回复

枚举第一排各位置是否点击,应该是因为原来第一排部分的1变为0,可能得到全局最优解,而且第一排决定了下面层的情况,所以要枚举这些可能。不用管原来第一排的对应元素是多少。

用户头像
不能说的秘密   2021-02-05 12:00      1    踩      回复

那为啥在求解全局最优解的时候不可以是由0变1呢?


用户头像
1e9+7   2019-08-03 21:56         踩      回复

复杂度不应该是n^22^n;
第一排枚举2^5每一种情况遍历n
(n-1)个格子;
复杂度不应该是2^25次方啊

用户头像
秦淮岸灯火阑珊   2019-08-04 07:35         踩      回复

第一排复杂度是$O(2^5)$,然后内部最大复杂度是$O(4 \times 5)$,不是$O(2^{20})$,一个judge的复杂度是$O(5 \times 5)$,因此配合上来就是,$O(2^5 \times (5+20+25))$

用户头像
秦淮岸灯火阑珊   2019-08-04 07:35         踩      回复

我说的是暴力是$O(2^{25}$.QwQ


用户头像
沐辰   2019-06-02 21:13         踩      回复

我能不能问下,为什么最坏是2^25次方,

用户头像
秦淮岸灯火阑珊   2019-08-04 07:36         踩      回复

暴力是$O(2^{25})$

用户头像
anonymous9527   2022-12-08 20:13         踩      回复

25个灯的01状态2^25


用户头像
itdef   2019-05-06 18:07         踩      回复

我也不太明白 为什么第一行要关注第一行为1的操作。
后来自己领悟出来了
因为如果关注为0的等 那么就要写成 if ((i>>(j-1) & 0) == 0)
不是那么简洁
另外 如果遍历所有情况 1和0 的情况是对称的
所以才有这种写法 不知道对不对?

用户头像
秦淮岸灯火阑珊   2019-05-06 19:36         踩      回复

第一行主要是因为我们要通过确定第一行才能确定下面行.一般来说check一种解答方法是否正确,主要是看能否AC,这个我也不好判断.关注0和关注一差不多是一样的.

用户头像
空银子   2021-10-25 14:20         踩      回复

if (i>>(j-1) & 1) 感觉是用来找第一行的操作的,如果为1就要进行修改


App 内打开
你确定删除吗?
1024
x

© 2018-2025 AcWing 版权所有  |  京ICP备2021015969号-2
用户协议  |  隐私政策  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标 qq图标
请输入绑定的邮箱地址
请输入注册信息