题目传送门
题目描述中已经将题意讲述的很明白了，但是知道了题意，很多人的想法都是暴力，但是一看到时间限制 10ms，都便头皮发麻了起来。（这是什么毒瘤数据！！！）
先声明这是 YJX 的题跟我没关系。
暴力的思路显然是对的 （毕竟对于黄题难度也没什么难度太大的算法）。
大致思路
有九种操作：即改变九个灯的明灭状态。
我们有以下两种思路：深度优先搜索和广度优先搜索。
当然对于这两种思路都涉及到比较两个状态是否相同（终止条件），显然如果对这两个 \(3\times 3\) 的表格一个一个比较是时间不允许的，于是我们引出了哈希这个概念 （故意卡哈希也不挑个大一点的数据）。
哈希&&位运算
“哈希”，OIWiki 上是这样形容的：
Hash 的核心思想在于，将输入映射到一个值域较小、可以方便比较的范围。
意思就是让我们把一种状态转化为一个数或者好比较的几个数去比较。
对于这个题，九个数都是 \(0\) 或 \(1\)，我们自然而然想到了二进制存图，举个例子：
1 0 1
0 1 0
1 0 1
这个图，我们就可以用二进制的数 \(101010101\) 即 \(341\) 来表示（对于进制转换的思想详见这个密码门题解（不是广告\doge））。
输入代码：
for(int i=1;i<=9;i++){int j=re();n+=j*(512>>i);}
目标状态就是 \(n\)。
那么将状态转化成数字之后该怎么进行操作呢？开第一个灯就是将第 \(1\)、\(2\)、\(4\) 个灯的状态取反，就是将二进制数从前往后数第 \(1\)、\(2\)、\(4\) 个数取反，如果原本这个状态是 \(000000000\) 那么改完后这个状态就是 \(110100000\) 即 \(416\)，所以对这一状态进行 \(1\) 操作即对这个状态代表的数异或上 \(416\)（异或可以理解为“不进位加法”）。于是这九个操作的本质都是将当前状态异或上一个数，具体这个数可以用计算器计算：
1.\(110100000:416\)
2.\(111010000:464\)
3.\(011001000:200\)
4.\(100110100:308\)
5.\(010111010:186\)
6.\(001011001:89\)
7.\(000100110:38\)
8.\(000010111:23\)
9.\(000001011:11\)
于是就有了这段广搜代码：
int ch[15]={0,416,464,200,308,186,89,38,23,11};//改变方式
void bfs()
{while(q.size()){int step=q.front().step,now=q.front().now;for(int i=1;i<=9;i++){int x=now^ch[i];if(vis[x])continue;command(x,step+1,i+'0');//加入队列，具体见下文}q.pop();}
}
路径存储
好那么现在问题来了：如何用广搜的队列存储走过的路径？
反正最后都是要输出的，就用字符串，字符串可以加一段字符串，也可以加一个单个的字符。
struct node
{int now,step;string op;
}p;
int vis[N];
void command(int x,int s,char i)
{node temp;temp.now=x;temp.op+=q.front().op;if(s!=1)temp.op+=' ';temp.op+=i;temp.step=s;q.push(temp);vis[x]=1,cnt++;if(x==n)//如果达到目标状态输出{wr(s),putchar('\n');cout<<temp.op;exit(0);}
}
由于我们是通过广搜得到的结果，那么我们得到的肯定是最短路径 （对于这个题深搜也是）。
完整代码奉上
#define N 1023
using namespace std;
struct node
{int now,step;string op;
}p;
int n;
int ch[15]={0,416,464,200,308,186,89,38,23,11};
int vis[N];
queue<node>q;
void command(int x,int s,char i)
{node temp;temp.now=x;temp.op+=q.front().op;if(s!=1)temp.op+=' ';temp.op+=i;temp.step=s;q.push(temp);vis[x]=1;if(x==n){wr(s),putchar('\n');cout<<temp.op;exit(0);}
}
void bfs()
{while(q.size()){int step=q.front().step,now=q.front().now;for(int i=1;i<=9;i++){int x=now^ch[i];if(vis[x])continue;command(x,step+1,i+'0');}q.pop();}
}
signed main()
{for(int i=1;i<=9;i++){int j=re();n+=j*(512>>i);}p.now=0,p.step=0,vis[0]=1;q.push(p);bfs();if(n==0)wr(0);//（小细节hack数据）puts("Impossible");//（其实不存在）return 0;
}
有同学的兴趣兴趣的同学可以考虑一下深搜，深搜可能比广搜要简单一些。