不会做,看了解题报告的分析,豁然开朗,
每个按钮按2次和没按效果是一样的。所以每个按钮或者按或者不按,一共有2^4=16种状态。枚举每个按钮是否按下,然后生成结果,排序输出即可(注意判重)。
另外灯1和灯7,2和8,3和9...是一样的因此当N>=6时只需处理前6个,排序时转换为10进制数, 输出时反复输出前6个的状态.
code:
/* ID: yueqiq LANG: C++ TASK: lamps */ #include <set> #include <map> #include <ctime> #include <queue> #include <cmath> #include <stack> #include <limits> #include <vector> #include <bitset> #include <string> #include <cstdio> #include <cstring> #include <fstream> #include <string.h> #include <iostream> #include <algorithm> #define ls rt<<1 #define rs rt<<1|1 #define Si set<int> #define LL long long #define pb push_back #define PS printf(" ") #define Vi vector<int> #define LN printf("\n") #define SD(a) scanf("%d",&a) #define PD(a) printf("%d",a) #define SET(a,b) memset(a,b,sizeof(a)) #define FF(i,a) for(int i(0);i<(a);i++) #define FD(i,a) for(int i(a);i>=(1);i--) #define FOR(i,a,b) for(int i(a);i<=(b);i++) #define FOD(i,a,b) for(int i(a);i>=(b);i--) #define readf freopen("lamps.in","r",stdin) #define writef freopen("lamps.out","w",stdout) const double pi = acos(-1.0); const int maxn = 50; const int BigP = 99999999; const int INF = 99999999; const int dx[]={0,1,0,-1}; const int dy[]={1,0,-1,0}; using namespace std; struct node{ int state,step; }; bool flag=true; int res[50],num,tmp[7]; bool vis[500]; int N,C,light[101],off[101],lcnt,ocnt; void bfs(){ node cur,tmp; queue<node> q; cur.state=63; cur.step=0; vis[63]=true; q.push(cur); while(!q.empty()){ tmp=q.front();q.pop(); if(tmp.step>C || tmp.step > 4) return; res[++num]=tmp.state; cur.state=tmp.state^63; cur.step=tmp.step+1; if(!vis[cur.state]){ q.push(cur); vis[cur.state]=true; } cur.state=tmp.state^42; if(!vis[cur.state]){ q.push(cur); vis[cur.state]=true; } cur.state=tmp.state^21; if(!vis[cur.state]){ q.push(cur); vis[cur.state]=true; } cur.state=tmp.state^36; if(!vis[cur.state]){ q.push(cur); vis[cur.state]=true; } } return; } void print(int sta){ int k=6,t;SET(tmp,0); while(sta){ t=sta%2; tmp[k--]=t; sta/=2; } FF(i,lcnt){ light[i]=(light[i]-1)%6+1; if(tmp[light[i]]!=1) return; } FF(i,ocnt){ off[i]=(off[i]-1)%6+1; if(tmp[off[i]]==1) return; } int pos=1; FOR(i,1,N){ printf("%d",tmp[pos++]); if(pos>6) pos=1; } flag=false; LN; return ; } int main (){ readf; writef; int tmp; SD(N);SD(C); while(~SD(light[lcnt])&&light[lcnt]!=-1){ lcnt++; } while(~SD(off[ocnt])&&off[ocnt]!=-1){ ocnt++; } bfs(); sort(res+1,res+num+1); FOR(i,1,num){ print(res[i]); } if(flag) puts("IMPOSSIBLE"); return 0; }