题目背景
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
0 1 1
1 0 0
1 0 1
输出 #1
2
——————————————————————————————————————
想了一会没有什么特别好的方法，所以直接搜索了，时间很充裕~
用二进制数表示九盏灯的开关状态，(2^9 = 512) 状态数允许完全被记录。
用 (way) 数组储存按下某栈灯时候会发生变化的灯的编号。
之后就是常规的广搜，(vis) 数组记录压缩后的每种状态实现需要的最少操作数。
代码如下：
#include <bits/stdc++.h>
#define MAX 666
using namespace std;
int init,vis[MAX];
int way[9][9]={{1,3,-1},{0,2,4,-1},{1,5,-1},
{0,4,6,-1},{1,3,5,7,-1},{2,4,8,-1},
{3,7,-1},{4,6,8,-1},{5,7,-1}};
queue<int> Q;
inline int read() {
int X=0,w=0; char ch=0;
while (!isdigit(ch)) w|=ch=='-',ch=getchar();
while (isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
return w?-X:X;
}
inline int open(int x,int opt) {
int pos=0;
while (way[opt][pos]!=-1) x^=(1<<way[opt][pos++]);
return x^=(1<<opt);
}
int main() {
memset(vis,-1,sizeof(vis));
for (int i=1;i<=9;i++) init<<=1,init+=read();
Q.push(init),vis[init]=0;
while (!Q.empty()) {
int now=Q.front(); Q.pop();
for (int i=0;i<9;i++) {
int tmp=open(now,i);
if (vis[tmp]==-1) vis[tmp]=vis[now]+1,Q.push(tmp);
}
}
printf("%d",vis[(1<<9)-1]);
return 0;
}