首页 > 代码库 > 拉灯游戏 搜索
拉灯游戏 搜索
你玩过“拉灯”游戏吗?25盏灯排成一个5x5的方形。每一个灯都有一个开关,游戏者可以改变它的状态。每一步,游戏者可以改变某一个灯的状态。游戏者改变一个灯的状态会产生连锁反应:和这个灯上下左右相邻的灯也要相应地改变其状态。
我们用数字“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 long13 const int maxn=20,inf=1000000;14 #define FILE "1"15 #define up(i,j,n) for(int i=j;i<=n;i++)16 #define down(i,n,j) for(int 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 h(int 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 down(i,5,1)up(j,0,4){s=s<<1;if(ch[i][j]==‘1‘)s++;}28 }29 int ans=10;30 void work(){31 //freopen(FILE".in","r",stdin);32 //freopen(FILE".out","w",stdout);33 scanf("%d",&n);34 memset(c,10,sizeof(c));35 while(n--){36 ans=10;37 up(i,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 if(b[x]<=3&&c[x]<=3)ans=min(ans,b[x]+c[x]);44 if(c[x]==3)continue;45 up(i,1,5)up(j,1,5){46 y=x;47 up(k,0,4){48 xx=i+dx[k],yy=j+dy[k];49 if(xx<1||yy<1||xx>5||yy>5)continue;50 y=y^(1<<(h(xx,yy)-1));51 }52 if(c[x]+1<c[y]){53 c[y]=c[x]+1;54 if(c[y]<3)q[++tail]=y;55 if(b[y]<=3&&c[y]<=3)ans=min(ans,b[y]+c[y]);56 if(c[y]==3)c[y]=90;57 }58 }59 }60 up(i,1,tail)c[q[i]]=90;61 printf("%d\n",ans==10?-1:ans);62 }63 }64 void first(){65 head=0,tail=0;int x,y;66 q[++tail]=(1<<25)-1;67 memset(b,10,sizeof(b));68 b[(1<<25)-1]=0;69 int xx,yy;70 while(++head<=tail){71 x=q[head];72 if(b[x]==3)continue;73 up(i,1,5)up(j,1,5){74 y=x;75 up(k,0,4){76 xx=i+dx[k],yy=j+dy[k];77 if(xx<1||yy<1||xx>5||yy>5)continue;78 y=y^(1<<(h(xx,yy)-1));79 }80 if(b[x]+1<b[y]){81 b[y]=b[x]+1;82 if(b[y]<3)q[++tail]=y;83 }84 }85 }86 }87 }88 int main(){89 using namespace OI;90 first();91 work();92 //printf("%d\n",clock());93 return 0;94 }
拉灯游戏 搜索
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。