你玩过“拉灯”游戏吗？25盏灯排成一个5×5的方形。每一个灯都有一个开关，游戏者可以改变它的状态。每一步，游戏者可以改变某一个灯的状态。游戏者改变一个灯的状态会产生连锁反应：和这个灯上下左右相邻的灯也要相应地改变其状态。
我们用数字“1”表示一盏开着的灯，用数字“0”表示关着的灯。下面这种状态
10111
01101
10111
10000
11011
在改变了最左上角的灯的状态后将变成：
01111
11101
10111
10000
11011
再改变它正中间的灯后状态将变成：
01111
11001
11001
10100
11011
给定一些游戏的初始状态，编写程序判断游戏者是否可能在6步以内使所有的灯都变亮
这也算是一道比较经典的问题了吧；
一种很快的做法是，枚举第一行改变了哪些灯的状态，然后我们就得到了第一行的灯的情况，然后为了满足末状态，第一行的未拉开的灯下面的那个灯一定要改变状态，这样就可以顺推下面的灯的状态，如果灯的状态都可以变成1，记录下步数比较即可；
第一遍的时候想如何暴力优化，想出了双向bfs搜索，可以先预处理下从末状态走三步的所有情况，然后在上面枚举的时候也只用走三步就可以了，25^3，枚举不会超过300，但由于常数比较大，容易被卡，我想出了双向bfs之后，便没有考虑在如何优化，上面的做法是后来知道的；
下面的是代码：
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<string> 5 #include<cstdlib> 6 #include<ctime> 7 #include<vector> 8 #include<algorithm> 9 #include<queue> 10 #include<map> 11 using namespace std; 12 #define LL long long 13 const int maxn=20,inf=1000000; 14 #define FILE "1" 15 #define upi,j,n) forint i=j;i<=n;i++) 16 #define downi,n,j) forint i=n;i>=j;i--) 17 namespace OI{ 18 short int b[35000000],c[35000000]; 19 int q[3000000],head,tail;//oj允许开这么大的数组我也是醉醉哒 20 int n; 21 inline int hint x,int y){return x*5+y-5;} 22 int dx[5]={0,0,0,-1,1},dy[5]={0,1,-1,0,0}; 23 char ch[6][6]; 24 int s; 25 void change){ 26 s=0; 27 downi,5,1)upj,0,4){s=s<<1;ifch[i][j]=='1')s++;} 28 } 29 int ans=10; 30 void work){ 31 //freopenFILE".in","r",stdin); 32 //freopenFILE".out","w",stdout); 33 scanf"%d",&n); 34 memsetc,10,sizeofc)); 35 whilen--){ 36 ans=10; 37 upi,1,5)scanf"%s",ch[i]); 38 change); 39 head=0,tail=0;q[++tail]=s;int x,y;c[s]=0; 40 int xx,yy; 41 while++head<=tail){ 42 x=q[head]; 43 ifb[x]<=3&&c[x]<=3)ans=minans,b[x]+c[x]); 44 ifc[x]==3)continue; 45 upi,1,5)upj,1,5){ 46 y=x; 47 upk,0,4){ 48 xx=i+dx[k],yy=j+dy[k]; 49 ifxx<1||yy<1||xx>5||yy>5)continue; 50 y=y^1<<hxx,yy)-1)); 51 } 52 ifc[x]+1<c[y]){ 53 c[y]=c[x]+1; 54 ifc[y]<3)q[++tail]=y; 55 ifb[y]<=3&&c[y]<=3)ans=minans,b[y]+c[y]); 56 ifc[y]==3)c[y]=90; 57 } 58 } 59 } 60 upi,1,tail)c[q[i]]=90; 61 printf"%d ",ans==10?-1:ans); 62 } 63 } 64 void first){ 65 head=0,tail=0;int x,y; 66 q[++tail]=1<<25)-1; 67 memsetb,10,sizeofb)); 68 b[1<<25)-1]=0; 69 int xx,yy; 70 while++head<=tail){ 71 x=q[head]; 72 ifb[x]==3)continue; 73 upi,1,5)upj,1,5){ 74 y=x; 75 upk,0,4){ 76 xx=i+dx[k],yy=j+dy[k]; 77 ifxx<1||yy<1||xx>5||yy>5)continue; 78 y=y^1<<hxx,yy)-1)); 79 } 80 ifb[x]+1<b[y]){ 81 b[y]=b[x]+1; 82 ifb[y]<3)q[++tail]=y; 83 } 84 } 85 } 86 } 87 } 88 int main){ 89 using namespace OI; 90 first); 91 work); 92 //printf"%d ",clock)); 93 return 0; 94 }
View Code