【描述】
在IOI98的节日宴会上，我们有N(10<=N<=100)盏彩色灯，他们分别从1到N被标上号码。 这些灯都连接到四个按钮：
按钮1：当按下此按钮，将改变所有的灯：本来亮着的灯就熄灭，本来是关着的灯被点亮。
按钮2：当按下此按钮，将改变所有奇数号的灯。
按钮3：当按下此按钮，将改变所有偶数号的灯。
按钮4：当按下此按钮，将改变所有序号是3*K+1(K>=0)的灯。例如：1,4,7...
一个计数器C记录按钮被按下的次数。当宴会开始，所有的灯都亮着，此时计数器C为0。
你将得到计数器C(0<=C<=10000)上的数值和经过若干操作后某些灯的状态。写一个程序去找出所有灯最后可能的与所给出信息相符的状态，并且没有重复。
【格式】
PROGRAM NAME: lamps
INPUT FORMAT:
(file lamps.in)
不会有灯会在输入中出现两次。
第一行: N。
第二行: C最后显示的数值。
第三行: 最后亮着的灯,用一个空格分开，以-1为结束。
第四行: 最后关着的灯,用一个空格分开，以-1为结束。
OUTPUT FORMAT:
(file lamps.out)
每一行是所有灯可能的最后状态(没有重复)。每一行有N个字符，第1个字符表示1号灯，最后一个字符表示N号灯。0表示关闭，1表示亮着。这些行必须从小到大排列（看作是二进制数）。
如果没有可能的状态，则输出一行'IMPOSSIBLE'。
【分析】
#include <cstdlib>
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <queue>
#include <algorithm>
const int Max=(<<)+;
using namespace std;
struct node
{
int state;
int step;//已经走过的步数
}sta;
int Check[],n,c,ans[Max];
int vis[(<<)+][],ans_point=;
inline int MOD(int t) {return (t%)==?:t%;}//取模运算
inline int get(int num,int i) {return (num&(<<i))==(<<i);}
void bfs();
bool check(int num);
int main()
{
int t,i,j;
//文件操作
freopen("lamps.in","r",stdin);
freopen("lamps.out","w",stdout);
memset(Check,-,sizeof(Check)); scanf("%d%d",&n,&c);
while (scanf("%d",&t) && t!=-) Check[MOD(t)]=;//最后亮着的
while (scanf("%d",&t) && t!=-) Check[MOD(t)]=;//最后黑着的
bfs();
sort(ans,ans+ans_point);
if (ans_point==) printf("IMPOSSIBLE\n");
for (i=;i<ans_point;i++)
{
for (j=;j<=n;j++) printf("%d",get(ans[i],MOD(j)-));
printf("\n");
}
return ;
}
void bfs()
{
memset(vis,,sizeof(vis));
queue<node>Q;
sta.state=(<<)-;sta.step=;
Q.push(sta);
while (!Q.empty())
{
node u=Q.front();Q.pop();
if (check(u.state) && u.step==c) {ans[ans_point++]=u.state;continue;}
node v;v=u;
v.step=u.step+;
//四种操作
v.state=v.state^((<<)-);if (vis[v.state][v.step]==) {vis[v.state][v.step]=;Q.push(v);}v=u;v.step=u.step+;
v.state=v.state^()^(<<)^(<<);if (vis[v.state][v.step]==) {vis[v.state][v.step]=;Q.push(v);}v=u;v.step=u.step+;
v.state=v.state^(<<)^(<<)^(<<);if (vis[v.state][v.step]==) {vis[v.state][v.step]=;Q.push(v);}v=u;v.step=u.step+;
v.state=v.state^()^(<<);if (vis[v.state][v.step]==) {vis[v.state][v.step]=;Q.push(v);}v=u;v.step=u.step+;
}
}
bool check(int num)
{
for (int i=;i<min(n,);i++) if (Check[i+]!=get(num,i) && Check[i+]!=-) return ;
return ;
}