当前位置: 首页 > article >正文

算法--解决熄灯问题

import numpy as np

# 初始化一个空列表,用于存储用户输入的每一行灯状态数据
line = []

# 通过循环让用户逐行输入灯的初始状态数据
for i in range(5):
    # 获取用户输入的第i行数据,并去除输入字符串两端可能存在的空白字符(如空格、换行等)
    line_input = input("请输入第" + str(i) + "行:").strip()
    # 将输入的字符串形式的数据转换为整数列表,例如 "101010" 会转换为 [1, 0, 1, 0, 1, 0],然后添加到line列表中
    line.append(list(map(int, line_input)))

# 将存储了用户输入的5行灯状态数据的列表转换为二维的numpy数组,方便后续进行矩阵操作
puzzle = np.array(line)

# 创建一个形状为(1, 6)的全零二维数组,数据类型为整数,用于在行方向上添加到puzzle数组的开头,作为额外的边界行(可能是为了符合特定算法逻辑对边界的处理需求)
zero_row = np.zeros((1, 6), dtype=int)
# 使用np.vstack函数将zero_row数组和puzzle数组按垂直方向(行方向)堆叠在一起,也就是在puzzle数组的开头添加了一行全零数据
puzzle = np.vstack((zero_row, puzzle))

# 创建一个形状为(6, 1)的全零二维数组,数据类型为整数,用于在列方向上添加到puzzle数组的两侧,作为额外的边界列(同样可能是为了满足后续算法对边界情况的处理)
zero_col = np.zeros((6, 1), dtype=int)
# 使用np.hstack函数将两个zero_col数组和中间的puzzle数组按水平方向(列方向)堆叠在一起,即在puzzle数组的最左边和最右边各添加了一列全零数据
puzzle = np.hstack((zero_col, puzzle, zero_col))

# 创建一个形状为(6, 8)的全零二维数组,数据类型为整数,用于记录每个位置的“按下”操作情况,初始时所有位置都为未按下(值为0)
press = np.zeros((6, 8), dtype=int)


def guess():
    """
    guess函数用于根据当前的灯状态(puzzle数组)和按下操作情况(press数组),判断当前按下操作是否能使得所有灯熄灭(满足特定条件)。
    具体是按照一定的规则更新press数组中对应位置的值,并检查最后一行灯的状态是否符合预期(这里推测是熄灭状态)。
    """
    # 遍历除了添加的边界行之外的“有效”行(索引从1到5,实际对应原来输入的5行数据所在的行范围)
    for r in range(1, 5):
        # 遍历除了添加的边界列之外的“有效”列(索引从1到7,实际对应原来输入的6列数据所在的列范围)
        for c in range(1, 7):
            # 根据周围灯的状态以及当前位置的按下操作情况,按照特定规则(可能是点灯游戏里的规则,通过异或操作实现状态变化逻辑)计算下一行对应位置的按下操作值,这里取余2实现类似异或的效果,确保结果为0或1
            press[r + 1][c] = (puzzle[r][c] + press[r][c] +
                               press[r - 1][c] + press[r][c - 1] +
                               press[r][c + 1]) % 2
    # 检查最后一行(索引为5,对应添加边界后的实际最后一行)灯的状态是否符合预期(根据某种规则判断是否全部熄灭等情况)
    for c in range(1, 7):
        if (press[5][c - 1] + press[5][c] + press[5][c + 1] + press[4][c]) % 2!= puzzle[5][c]:
            return 0
    return 1


def enumeration():
    """
    enumeration函数使用穷举法来尝试找到一种按下操作组合(通过修改press数组的值),使得所有灯最终熄灭(满足guess函数里判断的条件)。
    它通过不断改变press数组中第一个“有效”位置(press[1][1])的值,并按照一定规则逐步调整其他位置的值,反复调用guess函数进行判断,直到找到满足条件的组合为止。
    """
    # 只要guess函数返回0,说明当前按下操作组合不能使得所有灯熄灭,就继续循环尝试不同的按下操作组合
    while guess() == 0:
        # 先尝试改变press数组中第一个“有效”位置(press[1][1])的值,将其加1(因为初始值为0,这里开始尝试不同的按下情况)
        press[1][1] += 1
        c = 1
        # 当press[1][c]的值大于1时(由于这里只有0和1两种状态表示是否按下,大于1不符合要求),进行如下处理
        while press[1][c] > 1:
            # 将当前位置的值重置为0,表示不按下
            press[1][c] = 0
            c += 1
            # 只有当列索引小于8(在有效列范围内)时,才对下一个位置的值加1,继续尝试下一种按下情况
            if c < 8:
                press[1][c] += 1


# 调用enumeration函数开始通过穷举法寻找满足条件的按下操作组合
enumeration()

# 输出灯的初始状态,这里通过切片操作去除了之前添加的边界行和边界列,只显示用户最初输入的5行6列的灯初始状态数据
print("灯的初始状态:\n", puzzle[1:6, 1:7])
# 输出最终找到的满足条件的按下操作组合情况,同样通过切片操作去除边界部分,显示对应“有效”区域内的按下操作情况
print("按下结果为:\n", press[1:6, 1:7])
输出结果:

http://www.kler.cn/a/394460.html

相关文章:

  • 四:HTTP的诞生:它解决了哪些网络通信难题?
  • 前端面试笔试(二)
  • docker更改数据目录
  • ios swift开发--ios远程推送通知配置
  • Elasticsearch 8.16:适用于生产的混合对话搜索和创新的向量数据量化,其性能优于乘积量化 (PQ)
  • 字节跳动Android面试题汇总及参考答案(80+面试题,持续更新)
  • libigl 基于射线选择面片
  • 从JVM的角度,来分析为什么Java中是值传递?
  • 小程序服务商常见问题
  • 公共检查点(checkpoints)+探针(Probe)详解
  • 蓝队基础3 -- 身份与数据管理
  • 图论-代码随想录刷题记录[JAVA]
  • 11个c语言编程练习题
  • 干货满满!13个有趣又有用的Python 高级脚本
  • C#中的TCP通信
  • 低代码牵手 AI 接口:开启智能化开发新征程
  • ab (Apache Bench)的使用
  • 快速建造高品质音乐厅:声学气膜馆打造专业降噪空间—轻空间
  • N80PLC系列通信介绍(CAN与Modbus RTU)
  • 【商城系统搭建流程】
  • go+powershell脚本实现预填写管理凭据安装软件
  • 【WRF后处理】提取某要素数据并绘制地图
  • 基于Java Springboot剧本杀管理系统
  • webSocket的使用文档
  • MySQL【四】
  • 【.GetConnectionTimeoutException的2种情况分析】