【算法】费解的开关(递推)

这篇具有很好参考价值的文章主要介绍了【算法】费解的开关(递推)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目描述 

你玩过“拉灯”游戏吗?

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。

数据范围

0 < n ≤ 500

输入样例:

3
00111
01011
10001
11010
11100

11101
11101
11110
11111
11111

01111
11111
11111
11111
11111

输出样例:

3
2
-1

思路

        仔细观察可以发现,当第一排的灯状态确定之后,第2,3,4,5排的灯状态也就确定了。

第一步:搜索第一排灯开关状态改变或不改变(一共有32种结果)

第二步:根据第一排的灯的状态判断第二排的灯的开关是否需要改变状态(若前一排的灯为0,则改变它下面的那盏灯开关的状态),以此类推到第五排。

第三步:判断最后一排的灯是否全亮,若全部为亮,则比较开关改变的次数。若不全为亮,则进行下一次循环(进入第一步)。文章来源地址https://www.toymoban.com/news/detail-781445.html

代码 

#include<bits/stdc++.h>
using namespace std;
char str[6][6];
char cpy[6][6];
int dx[5] = {1,-1,0,0,0};
int dy[5] = {0,0,-1,1,0};
void turn(int x,int y)
{
    for(int i = 0; i < 5; i ++)
    {
        int xx = x + dx[i];
        int yy = y + dy[i];
        if(xx < 0 || xx > 4 || yy < 0 || yy > 4) continue;
        if(str[xx][yy] == '1') str[xx][yy] = '0';
        else str[xx][yy] = '1';
    }
}

void solve()
{
    for(int i = 0; i < 5; i ++) cin >> str[i];
    memcpy(cpy,str,sizeof str);// 对数组进行操作后需要进行复原
    int res = 10;
    for(int op = 0; op < 32; op ++)
    {
        int cnt = 0;
        memcpy(str,cpy,sizeof str);
        // 对第一行进行操作
        for(int i = 0; i < 5; i ++)
        {
            if(op >> i & 1)
            {
                turn(0,i);
                cnt ++;
            }
        }
        // 对剩下四行进行操作
        for(int i = 0; i < 4; i ++)
        {
            for(int j = 0; j < 5; j ++)
            {
                if(str[i][j] == '0')
                {
                    turn(i + 1,j);
                    cnt ++;
                }
            }
        }
        bool success = true;
        // 判断最后一行是否全亮
        for(int i = 0; i < 5; i ++)
        {
            if(str[4][i] == '0') success = false;
        }
        if(success && cnt < res) res = cnt;
    }
    if(res > 6) res = -1;
    cout << res << endl;
}


int main()
{
    int t;
    cin >> t;
    while(t --)
        solve();
    return 0;
}

到了这里,关于【算法】费解的开关(递推)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【第十五课】数据结构:堆(acwing-839模拟堆 / ph和hp数组的映射关系 /c++代码 )

    目录 注意点  代码如下  上篇已经详细解释过堆的内容,需要可以回顾一下。 【第十五课】数据结构:堆 这里关注这道题提出几个注意点。  这道题有几个需要注意的点: ①没有事先给出完整的数组,而是靠我们一次次操作进行插入。因此,要定义一个size变量记录插入数

    2024年01月25日
    浏览(39)
  • 算法 数据结构分类 数据结构类型介绍 数据结构线性非线性结构 算法合集 (一)

     数据结构分为:                            a.线性结构                            b.非线性结构  a.线性结构:                       数据与结构存在一对一的线性关系; a . 线性结构 存储 分为:                                   顺序存储

    2024年02月10日
    浏览(53)
  • 【算法与数据结构】--算法应用--算法和数据结构的案例研究

    一、项目管理中的算法应用 在项目管理中,算法和数据结构的应用涉及项目进度、资源分配、风险管理等方面。以下是一些案例研究,展示了算法在项目管理中的实际应用: 项目进度管理 : 甘特图算法 :甘特图是一种项目进度管理工具,它使用甘特图算法来展示项目任务

    2024年02月08日
    浏览(58)
  • 数据结构与算法设计分析—— 数据结构及常用算法

    1、顺序表与链表 线性表是 线性结构 ,是包含n个数据元素的有限序列,通过顺序存储的线性表称为 顺序表 ,它是将线性表中所有元素按照其逻辑顺序,依次存储到指定存储位置开始的一块连续的存储空间里;而通过链式存储的 链表 中,每个结点不仅包含该元素的信息,还

    2024年02月07日
    浏览(62)
  • 数据结构和算法——数据结构

    目录 线性结构  队列结构的队列 链表结构的队列 链表的面试题 单向链表应用场景 约瑟夫环问题 栈结构 中缀表达式 前缀表达式 后缀表达式 非线性结构 图 递归解决迷宫问题 递归解决八皇后问题 顺序存储方式,顺序表 常见的顺序存储结构有:数组、队列、链表、栈 链式存

    2024年02月07日
    浏览(56)
  • 数据结构与算法 --- 数据结构绪论

    早期人们都把计算机理解为数值计算工具,就是感觉计算机当然是用来计算的,所以计算机解决问题,应该是先从具体问题中抽象出一个适当的数据模型,设计出一个解此数据模型的算法,然后再编写程序,得到一个实际的软件。 可现实中,我们更多的不是解决数值计算的问

    2024年02月14日
    浏览(54)
  • 数据结构与算法——数据结构有哪些,常用数据结构详解

    数据结构是学习数据存储方式的一门学科,那么,数据存储方式有哪几种呢?下面将对数据结构的学习内容做一个简要的总结。 数据结构大致包含以下几种存储结构: 线性表,还可细分为顺序表、链表、栈和队列; 树结构,包括普通树,二叉树,线索二叉树等; 图存储结构

    2024年02月15日
    浏览(63)
  • 【数据结构与算法】不就是数据结构

      嗨喽小伙伴们你们好呀,好久不见了,我已经好久没更新博文了!之前因为实习没有时间去写博文,现在已经回归校园了。我看了本学期的课程中有数据结构这门课程(这么课程特别重要),因为之前学过一点,所以就想着深入学习一下子。毕竟这门课程对于 考研 和 就业

    2024年02月07日
    浏览(49)
  • 【数据结构与算法】1.数据结构绪论

    📚博客主页:爱敲代码的小杨. ✨专栏:《Java SE语法》 ❤️感谢大家点赞👍🏻收藏⭐评论✍🏻,您的三连就是我持续更新的动力❤️ 🙏小杨水平有限,欢迎各位大佬指点,相互学习进步! 数据结构是计算机中存储、组织数据的方式。 数据结构是一种具有一定逻辑关系,

    2024年01月23日
    浏览(54)
  • 数据结构与算法——什么是数据结构

    当你决定看这篇文章,就意味着系统学习数据结构的开始。下面我们先来讲什么是数据结构。 数据结构,直白地理解,就是研究数据的存储方式。 我们知道,数据存储只有一个目的,即为了方便后期对数据的再利用,就如同我们使用数组存储  {1,2,3,4,5}  是为了后期取得它们

    2024年02月15日
    浏览(55)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包