企业官网建设流程全解析

P10449 费解的开关

题目描述

你玩过“拉灯”游戏吗？

25 2525盏灯排成一个5 × 5 5 \times 55×5的方形。

每一个灯都有一个开关，游戏者可以改变它的状态。

每一步，游戏者可以改变某一个灯的状态。

游戏者改变一个灯的状态会产生连锁反应：和这个灯上下左右相邻的灯也要相应地改变其状态。

我们用数字1 11表示一盏开着的灯，用数字0 00表示关着的灯。

下面这种状态

10111 01101 10111 10000 11011

在改变了最左上角的灯的状态后将变成：

01111 11101 10111 10000 11011

再改变它正中间的灯后状态将变成：

01111 11001 11001 10100 11011

给定一些游戏的初始状态，编写程序判断游戏者是否可能在6 66步以内使所有的灯都变亮。

输入格式

第一行输入正整数n nn，代表数据中共有n nn个待解决的游戏初始状态。

以下若干行数据分为n nn组，每组数据有5 55行，每行5 55个字符。

每组数据描述了一个游戏的初始状态。

各组数据间用一个空行分隔。

输出格式

一共输出n nn行数据，每行有一个小于等于6 66的整数，它表示对于输入数据中对应的游戏状态最少需要几步才能使所有灯变亮。

对于某一个游戏初始状态，若6 66步以内无法使所有灯变亮，则输出-1。

输入输出样例 #1

输入 #1

3 00111 01011 10001 11010 11100 11101 11101 11110 11111 11111 01111 11111 11111 11111 11111

输出 #1

3 2 -1

说明/提示

测试数据满足0 < n ≤ 500 0 < n \le 5000<n≤500。

C++实现

#include<bits/stdc++.h>usingnamespacestd;queue<int>q;intans,x;shortl[1<<26];//省空间intqf(intx,inty){//改变灯的状态x^=(1<<y);if(y>4)x^=(1<<(y-5));if(y<20)x^=(1<<y+5);if(y%5!=0)x^=(1<<y-1);if(y%5<4)x^=(1<<(y+1));returnx;}voidbfs(){memset(l,-1,sizeofl);q.push((1<<25)-1);l[(1<<25)-1]=0;while(!q.empty()){intt=q.front();q.pop();if(l[t]>=6)break;for(inti=0;i<25;i++){if(l[qf(t,i)]==-1){q.push(qf(t,i));l[qf(t,i)]=l[t]+1;}}}return;}signedmain(){intn;cin>>n;bfs();while(n--){intx=0;for(inti=0;i<5;i++){for(intj=0;j<5;j++){intt;scanf("%1d",&t);if(t)x=x|(1<<(i*5+j));}}cout<<l[x]<<endl;}return0;//好习惯}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容