自动搬运

查看原文

来自洛谷，原作者为

	Uranus **

搬运于2025-08-24 21:33:16，当前版本为作者最后更新于2018-06-10 16:22:40，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

** 2018.6.10 华师一机房 **

---

原题：P2040 打开所有的灯

题目背景

pmshz在玩一个益(ruo)智(zhi)的小游戏，目的是打开九盏灯所有的灯，这样的游戏难倒了pmshz。。。

题目描述

这个灯很奇(fan)怪(ren)，点一下就会将这个灯和其周围四盏灯的开关状态全部改变。现在你的任务就是就是告诉pmshz要全部打开这些灯。

例如

0 1 1

1 0 0

1 0 1

点一下最中间的灯【2,2】就变成了

0 0 1

0 1 1

1 1 1

再点一下左上角的灯【1,1】就变成了

1 1 1

1 1 1

1 1 1

达成目标。最少需要2步。

输出2即可。

输入输出格式

输入格式：

九个数字，3*3的格式输入，每两个数字中间只有一个空格，表示灯初始的开关状态。（0表示关，1表示开）

输出格式：

1个整数，表示最少打开所有灯所需要的步数。

输入输出样例

输入样例#1：

0 1 1
1 0 0
1 0 1

输出样例#1：

2

说明

这个题水不水，就看你怎么考虑了。。。。

---

明显的搜索练手题，可以快速用 DFS 完成，那么写写试试吧！

DFS思路

引理：

同一个开关不会被同时使用两次。

证明：

这不废话嘛用了两次就回去了啊，这还用证？

证毕。

（不要在意这个证明）

通过我们严谨的证明，我们知道，同一个开关不可能被使用两次，所以我们就可以放心大胆地直接深度优先搜索了。可以用G数组表示目前灯的开关状态，用use数组表示开关是否用过（用过为1，未用过为0），再加上数据范围较小，总的运算次数不会超过O(9^9)，可以实现。

实现时间	程序耗时	占用内存	最终得分
10min	108ms	2113KB	100

代码：

#include<iostream>
using namespace std;
int G[5][5],ans=10;///由题可知，答案不会超过10，所以ans的初始值为10
bool use[5][5];///判断是否用过
///小技巧：用a和b两个数组快速完成位置变换
int a[5]={+0,+0,+1,-1,0};
int b[5]={+1,-1,+0,-0,0};
bool check()///判断函数
{
    for(int i=1;i<=3;i++)
        for(int j=1;j<=3;j++)
            if(!G[i][j])
                return false;
    return true;
}
void change(int x,int y)///变化函数
{
    for(int i=0;i<5;i++) G[x+a[i]][y+b[i]]=1-G[x+a[i]][y+b[i]];
}
void dfs(int step)///主体部分
{
    if(step>=ans) return ;///最(mei)优(shen)剪(me)枝(yong)
    if(check()) ans=min(ans,step);///找到答案
    else
    for(int i=1;i<=3;i++)
        for(int j=1;j<=3;j++)
            if(!use[i][j])
            {
                use[i][j]=1;
                change(i,j);
                dfs(step+1);
                ///回溯
                use[i][j]=0;
                change(i,j);
            }
}
int main()
{
    for(int i=1;i<=3;i++)
        for(int j=1;j<=3;j++)
            cin>>G[i][j];
    dfs(0);
    cout<<ans;
    return 0;
}

优点：写起来简单而且好想。

缺点：数据范围过大时比较鸡肋，容易 TLE 。

---

BFS+进制运算思路

其实一开始我看到这道题的时候是没有想到一个开关只能按一次的，所以就想打 BFS ，用方便判断是否到达目标的 string 储存当前状态，用方便判重的 STL 自带的 set 判断是否重复出现，这样就可以规避 DFS 思路的思考。本来代码打的好好的，突然脑子一糊涂，想着：“咦，只有九盏灯诶，可以用二进制储存啊，肯定也不会超过 1024 ，不是很方便吗”。然后 5min 打完的代码花了 20min ......

不过不得不说二进制运算和 BFS 是真的快，根本美好什么时间就运算完了，那就让 STL 见鬼去吧！

实现时间	程序耗时	占用内存	最终得分
23min	0ms	2062KB	100

代码：

#include<iostream>
using namespace std;
int tmp,h,t,step[100000];///step数组储存步数（也就是使用的开关数）
int bfs[100000];///储存当前的灯光状态
bool use[300];///判重数组，事实证明不是不到1024，连256都到不了
int change(int x,int pos)///神仙一般的变换函数！引以为傲但是超级难想，因为这个本机测试的时候RE了好多次
{
    int re=x;
    re^=1<<(8-pos);
    if(pos%3!=0) re^=1<<(9-pos); ///开关不在第一列
    if(pos%3!=2) re^=1<<(7-pos); ///开关不在最后一列
    if(pos/3!=0) re^=1<<(11-pos);///开关不在第一排
    if(pos/3!=2) re^=1<<(5-pos); ///开关不在最后一排
    return re;
}
int main()
{
    for(int i=0;i<9;i++)
    {
        cin>>tmp;
        bfs[0]=bfs[0]*2+tmp;///转换为二进制储存
    }
    use[bfs[0]]=true;
    while(h<=t)///标准BFS
    {
        for(int i=0;i<9;i++)
        {
            bfs[++t]=change(bfs[h],i);
            step[t]=step[h]+1;
            if(bfs[t]==(1<<9)-1)///到达最终状态
            {
                cout<<step[t];
                return 0;
            }
            if(use[bfs[t]]) t--;
            else use[bfs[t]]=true;
        }
        h++;
    }
    return 0;
}

优点：跑得超级快，时空甩 DFS 一大截。

缺点：累【这是真的】。

一定要提一下的一个小东西！

在我第一次用 DFS 思路写的时候其实是用 string 储存的，变换函数也和二进制思路比较相似，即：

string act(string a,int pos)
{
    string re=a;
    re[pos]=(a[pos]='0'?'1':'0');
    if(pos%3!=0) re[pos-1]=a[pos-1]='0'?'1':'0';
    if(pos%3!=2) re[pos+1]=a[pos+1]='0'?'1':'0';
    if(pos/3!=0) re[pos-3]=a[pos-3]='0'?'1':'0';
    if(pos/3!=2) re[pos+3]=a[pos+3]='0'?'1':'0';
    return re;
}

甚至还用了我从来没用过的三目运算符。

可是结果是60分，3WA。虽然错的不是这里，但我还是要说一下：用三目运算符一定要打括号，你又不是OYYZ，你不知道运算符优先级啊喂。

正确写法：

string act(string a,int pos)
{
    string re=a;
    re[pos]=(a[pos]='0'?'1':'0');
    if(pos%3!=0) re[pos-1]=(a[pos-1]='0')?'1':'0';
    if(pos%3!=2) re[pos+1]=(a[pos+1]='0')?'1':'0';
    if(pos/3!=0) re[pos-3]=(a[pos-3]='0')?'1':'0';
    if(pos/3!=2) re[pos+3]=(a[pos+3]='0')?'1':'0';
    return re;
}

2018.6.11 update1

好吧其实就错在这里，三目运算符中要打==判断而不是=。。。

真·正确写法：

string act(string a,int pos)
{
    string re=a;
    re[pos]=(a[pos]=='0'?'1':'0');
    if(pos%3!=0) re[pos-1]=(a[pos-1]=='0')?'1':'0';
    if(pos%3!=2) re[pos+1]=(a[pos+1]=='0')?'1':'0';
    if(pos/3!=0) re[pos-3]=(a[pos-3]=='0')?'1':'0';
    if(pos/3!=2) re[pos+3]=(a[pos+3]=='0')?'1':'0';
    return re;
}

或者写成：

string act(string a,int pos)
{
    string re=a;
    re[pos]=(a[pos]=='0')+'0';
    if(pos%3!=0) re[pos-1]=(a[pos-1]=='0')+'0';
    if(pos%3!=2) re[pos+1]=(a[pos+1]=='0')+'0';
    if(pos/3!=0) re[pos-3]=(a[pos-3]=='0')+'0';
    if(pos/3!=2) re[pos+3]=(a[pos+3]=='0')+'0';
    return re;
}

---

今天的题目总结就到这里吧，还有个 diggersun 老师提到的循环算法，还没有写，但是听说超级快，有时间再来补一下吧！