网站建设人员需求,现在币圈有那些私募网站做的好,网站建设的作用,专做企业网站的费解的开关
你玩过“拉灯”游戏吗#xff1f;
25 盏灯排成一个 55 的方形。
每一个灯都有一个开关#xff0c;游戏者可以改变它的状态。
每一步#xff0c;游戏者可以改变某一个灯的状态。
游戏者改变一个灯的状态会产生连锁反应#xff1a;和这个灯上下左右相邻的灯也…费解的开关
你玩过“拉灯”游戏吗
25 盏灯排成一个 5×5 的方形。
每一个灯都有一个开关游戏者可以改变它的状态。
每一步游戏者可以改变某一个灯的状态。
游戏者改变一个灯的状态会产生连锁反应和这个灯上下左右相邻的灯也要相应地改变其状态。
我们用数字 1表示一盏开着的灯用数字 0 表示关着的灯。
下面这种状态
10111
01101
10111
10000
11011在改变了最左上角的灯的状态后将变成
01111
11101
10111
10000
11011再改变它正中间的灯后状态将变成
01111
11001
11001
10100
11011给定一些游戏的初始状态编写程序判断游戏者是否可能在 6 步以内使所有的灯都变亮。
输入格式
第一行输入正整数 n代表数据中共有 n个待解决的游戏初始状态。
以下若干行数据分为 n 组每组数据有 5 行每行 5 个字符。
每组数据描述了一个游戏的初始状态。
各组数据间用一个空行分隔。
输出格式
一共输出 n 行数据每行有一个小于等于 6 的整数它表示对于输入数据中对应的游戏状态最少需要几步才能使所有灯变亮。
对于某一个游戏初始状态若 6 步以内无法使所有灯变亮则输出 −1。
数据范围
0n≤500
输入样例
3
00111
01011
10001
11010
1110011101
11101
11110
11111
1111101111
11111
11111
11111
11111输出样例
3
2
-1解析
观察这个题目首先可以把他当作一个典型的01图标问题解决这种问题我们一般使用dfs深度遍历搜索
在这里先使用递归来解题感兴趣的同学可以把他翻译成遍历。
针对于题目给的数组先把他化成图
10111
01101
10111
10000
11011我们可以试着玩游戏一样把他全点亮该怎么做呐
首先在第一行不变的前提下因为要保护第一行如果直接动第一行会造成无限的死循环前后的操作会彼此影响导致不断重复
我们操作第二行点击第二行的第一个 第一行就解脱了这时我们专注于操作第二行就可以了同理在保护第二行的前提下所以我们只能操作第三行。
打开12这个开关 为了点亮22所以点击23 为了点亮42关闭开关43 至此前两行操作完成点击14 依次点击243454得到 操作最后一行得到 很显然这种状态无法完成。
因为我们对下面的每一行的操作有大量的重复工作比如说在保护第二行的基础上对第三行进行操作以此类推我们完全可以把它封装成一个函数来实现。
int check(int cnt)//这里的cnt其实是我们传入的k(已经执行的操作数)
{int sumcnt;for(int i1;i5;i)for(int j1;j5;j)b[i][j]a[i][j];//复制出一个可操作数组for(int i1;i4;i)//不对最后一行进行操作因为最后一行不能在通过保护最后一行来操作下一行来实现了。{for(int j1;j5;j){if(!b[i][j])//找到熄灭的灯{sum;b[i][j]!b[i][j];//把目标开关下面的开关点亮再把它四周的开关取反b[i1][j]!b[i1][j];b[i1][j-1]!b[i1][j-1];b[i1][j1]!b[i1][j1];b[i2][j]!b[i2][j];}}}for(int i1;i5;i)if(!b[5][i])return Inf;//检测最后一行如果存在熄灭的灯就说明这次递归失败无解return sum;//成功则返回操作数
}在代码写到这里的时候我们发现。我们并没有对第一行进行过任何的操作很明显这样会漏解。
我们延续这种思路其实在遍历每一种情况的时候无非是选或者不选两种情况。这时我们就得出了状态转移方程 这里的cnt表示列k表示操作数当操作数1的时候表示打开开关操作数不变时表示没有操作。cnt1表示前进一列
由此我们可以写出一个简单个dfs
int dfs(int cnt,int k)
{if(cnt5)//到达第5列以后的判断(check)//按下开关时对周围开关的操作dfs(cnt1,k1);//按下这个开关//写递归最重要的就是还原案发现场dfs(cnt1,k);//不按下这个开关
}在这里我们只对第一行的操作进行了递归为什么不对每一行都进行递归呐
因为针对于下面的操作都是寻找未打开的开关有明确的指向性而对于第一行的操作没有明确的目的我们只是为了不遗漏答案。
int dfs(int cnt,int k)
{if(cnt5){ansmin(ans,check(k));//对每一种合法操作进行比较寻找操作数最小的操作数//ans的初值设为IMT_MAX;return 0;}//按下开关时对周围开关的操作a[1][cnt]!a[1][cnt];a[1][cnt-1]!a[1][cnt-1];a[1][cnt1]!a[1][cnt1];a[2][cnt]!a[2][cnt];dfs(cnt1,k1);//按下这个开关//写递归最重要的就是还原案发现场a[1][cnt]!a[1][cnt];a[1][cnt-1]!a[1][cnt-1];a[1][cnt1]!a[1][cnt1];a[2][cnt]!a[2][cnt];dfs(cnt1,k);//不按下这个开关
}设计主函数
int main()
{scanf(%d,t);while(t--){for(int i1;i5;i)for(int j1;j5;j)scanf(%1d,a[i][j]);ansInf;dfs(1,0);if(ans7)printf(%d\n,ans);//操作数是否小于等于6步。else printf(-1\n);}return 0;
}完整代码:
#include cstdio
#include iostream
#include queue
#include cstring
#define Inf 0x3f3f3f
#define ll long long
using namespace std;
int t;
int ans;
int a[10][10];
int b[10][10];
int check(int cnt)//判断第一行的条件是否成立
{int sumcnt;for(int i1;i5;i)for(int j1;j5;j)b[i][j]a[i][j];for(int i1;i4;i){for(int j1;j5;j){if(!b[i][j]){sum;b[i][j]!b[i][j];b[i1][j]!b[i1][j];b[i1][j-1]!b[i1][j-1];b[i1][j1]!b[i1][j1];b[i2][j]!b[i2][j];}}}for(int i1;i5;i)if(!b[5][i])return Inf;return sum;}
int dfs(int cnt,int k)
{if(cnt5){ansmin(ans,check(k));return 0;}a[1][cnt]!a[1][cnt];a[1][cnt-1]!a[1][cnt-1];a[1][cnt1]!a[1][cnt1];a[2][cnt]!a[2][cnt];dfs(cnt1,k1);//按下这个开关a[1][cnt]!a[1][cnt];a[1][cnt-1]!a[1][cnt-1];a[1][cnt1]!a[1][cnt1];a[2][cnt]!a[2][cnt];dfs(cnt1,k);//不按下这个开关
}
int main()
{scanf(%d,t);while(t--){for(int i1;i5;i)for(int j1;j5;j)scanf(%1d,a[i][j]);ansInf;dfs(1,0);if(ans7)printf(%d\n,ans);else printf(-1\n);}return 0;
}
