当前位置：首页 > news >正文

费解的开关

news 来源：原创 2024/5/11 4:51:17

你玩过“拉灯”游戏吗？

盏灯排成一个 5×5

的方形。

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

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

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

我们用数字 1

表示一盏开着的灯，用数字 0

表示关着的灯。

下面这种状态

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

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

给定一些游戏的初始状态，编写程序判断游戏者是否可能在 6

步以内使所有的灯都变亮。

输入格式

第一行输入正整数 n

，代表数据中共有 n

个待解决的游戏初始状态。

以下若干行数据分为 n

组，每组数据有 5 行，每行 5

个字符。

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

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

输出格式

一共输出 n

行数据，每行有一个小于等于 6

的整数，它表示对于输入数据中对应的游戏状态最少需要几步才能使所有灯变亮。

对于某一个游戏初始状态，若 6

步以内无法使所有灯变亮，则输出 −1

。

数据范围

0<n≤500

输入样例：

输出样例：

3
2
-1

思路：

一开始想着用dfs去硬跑，发现，嘶，出来了但是没有完全跑出来。

后来想想，题目说的是要6步以内能不能成功，那么也就是说步骤要尽可能的少，因此通过题意可以想到，如果第一行有灯是关着的，其实只要去操作第二行就行了，这样相应的就可以变亮了。所以其实第一行的状态就已经能确定答案了，那么这个时候我们只要枚举第一行的状态。

由于一行只有五个数字，那么一共也就只有32种情况（2^ 5）。

为什么要枚举第一行情况：去寻找最小步骤、

每一次再通过ans = min(ans, step);把最小步数存一下，就能找到最优解

#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<stack>
#include<string>
#include<algorithm>
#include<unordered_map>
#include<map>
#include<bitset>
#include<cstring>
#include <unordered_set>
//#include<priority_queue>
#include<queue>
#include<deque>
#include<set>
#include<stdlib.h>
#define dbug cout<<"*****hear*****"<<endl;
#define rep(a,b,c) for(ll a=b;a<=c;a++)
#define per(a,b,c) for(ll a=b;a>=c;a--)
#define no cout<<"NO"<<endl;
#define yes cout<<"YES"<<endl;
#define endl "\n"//交互题一定要关！！！！！！！！！
#define lowbit(x) (x&-x)
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//priority_queue<int,vector<int>,greater<int> >q;
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> PII;
typedef pair<long double,long double> PDD;ll  INF = 0x3f3f3f3f;
//const ll LINF=LLONG_MAX;
// int get_len(int x1,int y1,int x2,int y2)
// {
//   return (x2-x1)*(x2-x1) + (y2-y1)*(y2-y1);
// }
const ll N = 2e5+ 10;
// const ll mod1 =998244353;const ll mod2 =1e9+7;
// const ll hash_num = 3e9+9;
ll n,m,ca;
ll arr[N],brr[N],crr[N],drr[N];
//ll h[N],ne[N],e[N],w[N],book[N],idx;
//ll idx;// void add(ll a, ll b , ll c)
// {
//   e[idx] = b, w[idx] = c,ne[idx] = h[a], h[a] =idx ++ ; 
// }int dx[]={0,1,0,-1,0};
int dy[]={0,0,1,0,-1};
char mp[9][9];
char mmp[9][9];void turn(ll x,ll y)//反转操作
{rep(i,0,4){int tx=dx[i]+x , ty=dy[i]+y;if(tx<0 || tx>=5 || ty>=5 || ty<0)continue;mp[tx][ty] ^= 1;}
}void solve()
{ll ans=20;rep(i,0,4){cin >> mp[i];}rep(op,0,31){memcpy(mmp,mp,sizeof mp);//把原始数组备份一下，然后操作g，操作完了还原，然后再操作ll step=0;rep(i,0,4){if( op >> i & 1){step++;turn(0,i);}}// 数字2 对应了 00010 表示第2个位置的按一下// 00010 >> 1 & 1  是1 所以turn(0, 1) 就是第一行第二个位置// 数字3 对应了00011 表示第1 和第2个位置的按一下rep(i,0 ,3){rep(j,0,4){if(mp[i][j]=='0'){step++;turn(i+1,j);}}}ll f=0;rep(i,0,4){if(mp[4][i]=='0'){f=1;break;}}if(!f)ans=min(ans,step);memcpy(mp,mmp,sizeof mp);}if(ans>6){cout << -1 << endl;}else{cout << ans <<endl;}
}int main()
{// IOS;ll _;_=1;//scanf("%lld",&_);cin>>_;ca=1;while(_--){solve(); ca++;}    return 0;
}