【题目总结】P2040 打开所有的灯
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 老师提到的循环算法，还没有写，但是听说超级快，有时间再来补一下吧！