算法学习之每日一题Day4

题目    费解的开关

一、有关题目(涉及算法:递推,模拟)

1.题目来源:《算法竞赛进阶指南》

                       Acwing 95

2.题目链接 https://www.acwing.com/problem/content/description/97/

3.题目描述

你玩过“拉灯”游戏吗?

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

二、抽象模型

由题意得,

1.最终结果与开关按下的顺序无关。

2.每个格子最多只能按一次。

对2.进行解释:

因为,同一个格子的“开关”按偶数次相当于没有按,按奇数次相当于按了1次,因为该题让寻找最少步数,所以每个格子的“开关”要么按一次,要么就不按。

由此,可以发现,如果一行一行按开关,前一行暗的格子只能按下当前行开关来控制,而前一行亮的格子为了保持不变,必不能按下当前行对应位置的开关。

即,从第二行开始,当前行的按开关情况只由前一行确定。是一个递推的过程。

即,只需要枚举第一行的按开关情况,整个数组的情况都能确定,从而使算法大大简化。

三、时间复杂度分析

32 * 25 * 5 * 500 == 2000000 < 10^7

解释:

32:枚举第一行开关情况,有5个位置,每个位置都有按与不按两种可能,共32种情况。

25:第一行确定后大概有25个开关要按。

5:每按一个开关都要按五个位置。

500:共有500个测试数据。

四、知识储备

1.位运算

2.偏移量

在实现过程中可以利用1,2进行代码优化。

1.题目利用了位运算实现进制转化

具体位运算知识,见文章 https://mp.csdn.net/mp_blog/creation/editor/135893319

2.常见偏移量及处理方式

五、代码实现

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;

const int N = 6;

char g[N][N], backup[N][N];
int dx[5] = {-1, 1, 0, 0, 0}, dy[5] = {0, 0, -1, 1, 0};

int step, res;

void turn(int x, int y){ // 开关函数的具体实现
    for(int i = 0; i < 5; ++ i){
       int a = x + dx[i], b = y + dy[i];
       if(a < 0 || a >= 5 || b < 0 || b >= 5) continue;
       g[a][b] ^= 1; // 代码优化:'0'->'1', '1'->'0' 用异或运算
    }
}

int main(){
    int n;
    scanf("%d", &n); // 读入数据组数
    
    while(n--){
        
        res = 10;
        // 用字符数组模拟灯亮状态
        for(int i = 0; i < 5; ++ i){ // 按行读入每组里的具体数据
                scanf("%s", g[i]);
        }
        
        memcpy(backup, g, sizeof g); // 因为后续采用枚举方式,寻找最小步数,所以需要对数组进行备份
        
        // 进行枚举,寻找最小步数
        for(int op = 0; op < 32; ++ op){ // 由于题目特性,枚举第一行五个位置开关按下与否的情况(每个位置有2种选择:按下或不按)可以确定整个数据组的开关情况
            
        memcpy(g, backup, sizeof backup);
            
            step = 0;
            // 代码优化:利用位运算来进行进制转换,从而确定第一行每个位置开关按与不按的情况(也可以直接用递归来实现,这其实就是一个指数型枚举)
            for(int i = 0; i < 5; ++ i){ 
                if(op >> i & 1){
                    ++ step;
                    turn(0, i);
                }
            }
            
            // 从第一行开始,根据第该行的灯亮情况确定该下一行开关按下与否,依次递推
            for(int i = 0; i < 4; ++ i){
                for(int j = 0; j < 5; ++ j){
                    if(g[i][j] == '0'){
                        ++ step;
                        turn(i+1, j);
                    }
                }
            }
            
            //判断与更新
            bool dark = false;
            for(int i = 0; i < 5; ++ i){
                if(g[4][i] == '0'){
                   dark = true;
                   break; 
                }
            }
            
            if(!dark) res = min(res, step); // 更新最小步数
        }
        
        if(res > 6) printf("-1\n");
        else printf("%d\n", res);
    }

    return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/354798.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

范仲淹大直男逆袭,先天下之忧而忧

人在最艰苦时&#xff0c;最能体现英雄本色。 天底下最苦的是读书。读书要眼到、手到、心到&#xff0c;专心致志&#xff0c;灵活运用。 范仲淹读书很用功&#xff0c;每天煮一锅粥。等到第二天&#xff0c;粥凝固了&#xff0c;范仲淹把隔夜粥划为四块&#xff0c;早上吃两块…

Blender教程(基础)-初始用户界面-01

开始第一天的Blender学习、也是业余学习。希望记录下这一份学习的过程、并且分享给大家。今天带大家认识Blender这一款软件&#xff0c;先说说我为什么选择了Blender&#xff0c;我在软件市场找了好久&#xff0c;市场上其他雷同软件都是要么收费要么不好用&#xff0c;最终决定…

MATLAB知识点:向量元素的引用

讲解视频&#xff1a;可以在bilibili搜索《MATLAB教程新手入门篇——数学建模清风主讲》。​ MATLAB教程新手入门篇&#xff08;数学建模清风主讲&#xff0c;适合零基础同学观看&#xff09;_哔哩哔哩_bilibili 节选自第3章 3.2.2节 对向量元素的引用&#xff08;即提取向量…

如何将前后端分离(vue2+SpringBoot)项目部署到腾讯云服务器

如何将前后端分离&#xff08;vue2SpringBoot&#xff09;项目部署到腾讯云服务器 目录 如何将前后端分离&#xff08;vue2SpringBoot&#xff09;项目部署到腾讯云服务器 1、在选中目录地下新建2个文件夹 2、将打包好的前端项目和后端jar包上传到相应的目录下 3、将路径切…

MyBatis详解(5)-- MyBatis注解

MyBatis详解&#xff08;5&#xff09; 注解映射器xml配置文件的缺陷&#xff1a;常用注解1.基本注解&#xff1a;实现简单的增删改查操作。Insert 新增Options(useGeneratedKeys true, keyProperty "主键属性") 主键回填SelectKey ( statement "自增规则&qu…

Mysql大数据量分页优化

前言 之前有看过到mysql大数据量分页情况下性能会很差&#xff0c;但是没有探究过它的原因&#xff0c;今天讲一讲mysql大数据量下偏移量很大&#xff0c;性能很差的问题&#xff0c;并附上解决方式。 原因 将原因前我们先做一个试验&#xff0c;我做试验使用的是mysql5.7.2…

Matlab|【完全复现】基于价值认同的需求侧电能共享分布式交易策略

目录 1 主要内容 2 部分程序 3 程序结果 4 下载链接 1 主要内容 该程序完全复现《基于价值认同的需求侧电能共享分布式交易策略》&#xff0c;针对电能共享市场的交易机制进行研究&#xff0c;提出了基于价值认同的需求侧电能共享分布式交易策略&#xff0c;旨在降低电力市…

北京摇号政策梳理汇总

文章目录 政策梳理 家庭申请资格 家庭积分规则 参考资料 目前&#xff0c;北京车牌摇号实施的政策&#xff0c;主要是2021年1月1日的《<北京市小客车数量调控暂行规定>实施细则》。本文梳理了与博主本人直接相关的一些内容&#xff0c;可能对大部分网友也有帮助。 政…

基于springboot宠物领养系统

摘要 随着社会的不断发展和人们生活水平的提高&#xff0c;宠物在家庭中的地位逐渐上升&#xff0c;宠物领养成为一种流行的社会现象。为了更好地管理和促进宠物领养的过程&#xff0c;本文基于Spring Boot框架设计和实现了一套宠物领养系统。该系统以用户友好的界面为特点&…

有趣的移位操作符和位操作符(由浅入深轻松搞定!)

目录 1. 原码&#xff0c;反码&#xff0c;补码 2.移位操作符 2.1 左移操作符 2.2 右移操作符 3.位操作符 (&、|、^、~) 4.使用移位操作符和位操作符写一些有趣的代码~ 1.不能创建临时变量&#xff08;第三个变量&#xff09;&#xff0c;实现两个数的交换 2.编写代…

[echarts] 图表工具栏 toolbox

option{// 工具栏配置toolbox:{id:1, // 组件IDshow:true, // 是否显示工具栏orient:horizontal, // 工具栏 icon 的布局朝向itemSize:15, // 工具栏 icon 的大小itemGap:10, // 工具栏…

算法沉淀——双指针算法(leetcode真题剖析)

算法沉淀——双指针算法 01.移动零02.复写零03.快乐数04.盛最多水的容器05.有效三角形的个数06.和为s的两个数字07.三数之和08.四数之和 双指针算法&#xff08;Two Pointer Algorithm&#xff09;是一种常用于数组&#xff08;或链表&#xff09;操作的算法技巧。它的核心思想…

Kano模型

目录 1.介绍&#xff1a;2.Kano模型的作用&#xff1a;3.KANO模型使用场景&#xff1a;4.使用步骤&#xff1a;4.1设计问卷&#xff1a;4.2 数据分析4.2.1 KANO属性4.2.2 Better系数、Worse系数4.2.3 举例&#xff1a; 小结&#xff1a; 1.介绍&#xff1a; Kano模型是一种质量…

C#常见内存泄漏

背景 在开发中由于对语言特性不了解或经验不足或疏忽&#xff0c;往往会造成一些低级bug。而内存泄漏就是最常见的一个&#xff0c;这个问题在测试过程中&#xff0c;因为操作频次低&#xff0c;而不能完全被暴露出来&#xff1b;而在正式使用时&#xff0c;由于使用次数增加&…

【JavaScript 基础入门】02 JavaScrip 详细介绍

JavaScrip 详细介绍 目录 JavaScrip 详细介绍1. JavaScript 是什么2. JavaScript的作用3. HTML/CSS/JS 的关系4. 浏览器执行 JS 简介5. JavaScript 的组成6. JavaScript 的特点 1. JavaScript 是什么 JavaScript&#xff0c;通常缩写为 JS&#xff0c;是一种高级的&#xff0c;…

【SpringSpringBoot】概述

Spring&SpringBoot专题 【注】&#xff1a; 本专题围绕框架核心概念展开&#xff0c;渐进式深入总结学习、面试、开发经验&#xff0c;集中整理便于回顾 持续补充与施工中~~~~ 1.发展史 2.基本架构 Spring框架的基本架构是一个分层架构&#xff0c;包括多个模块&#x…

STL---stackqueue

一、stack 1.stack的介绍 stack介绍文档 https://legacy.cplusplus.com/reference/stack/stack/?kwstack 1. stack是一种容器适配器&#xff0c;专门用在具有后进先出操作的上下文环境中&#xff0c;其删除只能从容器的一端进行元素的插入与提取操作。 2. stack是作为容器适…

AI技术大揭秘:探索人工智能的核心领域与必备技能

随着人工智能的不断进步&#xff0c;AI技术在各个领域都发挥着越来越关键的作用。想要成为AI领域的从业者&#xff0c;不仅需要对整体格局有清晰认识&#xff0c;更要掌握关键技术和必备技能。本文将深入解析AI的核心技术领域&#xff0c;以及在这个前沿领域里需要掌握的技能。…

Java_集合类

集合可以看作是一个容器&#xff0c;集合中的各个对象&#xff0c;很容易将其从集合中取出来&#xff0c;也很容易将其存放到集合中&#xff0c;还可以按照一定的顺序进行摆放。JAVA中提供了不同的集合类&#xff0c;这些类具有不同的存储对象的方式&#xff0c;同时提供了相应…

04-JVM虚拟机-课堂笔记

04-JVM虚拟机 1. JVM虚拟机概述 1.4 对象的创建流程与内存分配 1.4.1 创建流程 1.4.2 对象内存分配方式 内存分配的方法有两种&#xff1a;不同垃圾收集器不一样 指针碰撞(Bump the Pointer) 空闲列表(Free List) 分配方法说明收集器指针碰撞(Bump the Pointer)内存地址…