首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >枚举——熄灯问题

枚举——熄灯问题

作者头像
Tyan
发布2019-05-25 22:54:26
6810
发布2019-05-25 22:54:26
举报
文章被收录于专栏:SnailTyanSnailTyan

版权声明:博客文章都是作者辛苦整理的,转载请注明出处,谢谢! https://cloud.tencent.com/developer/article/1433913

{}文章作者:Tyan

博客:noahsnail.com | CSDN | 简书

1. 枚举

枚举是基于逐个尝试答案的一种问题求解策略。

2. 熄灯问题(POJ1222)

  • 问题描述 有一个由按钮组成的矩阵,其中每行有6个按钮,共5行。每个按钮的位置上有一盏灯。当按下一个按钮后,该按钮以及周围位置(上边、下边、左边、右边)的灯都会改变一次。

如果灯原来是点亮的,就会被熄灭;如果灯原来是熄灭的,则会被点亮。在矩阵角上的按钮改变3盏灯的状态;在矩阵边上的按钮改变4盏灯的状态;其他的按钮改变5盏灯的状态。

与一盏灯毗邻的多个按钮被按下时,一个操作会抵消另一次操作的结果。对矩阵中的每盏灯设置一个初始状态。请你按按钮,直至每一盏等都熄灭。

  • 输入 5行组成,每一行包括6个数字(0或1)。相邻两个数字之间用单个空格隔开。0表示灯的初始状态是熄灭的,1表示灯的初始状态是点亮的。
  • 输出 5行组成,每一行包括6个数字(0或1)。相邻两个数字之间用单个空格隔开。其中的1表示需要把对应的按钮按下,0则表示不需要按对应的按钮。
  • 输入样例
0 1 1 0 1 0
1 0 0 1 1 1
0 0 1 0 0 1
1 0 0 1 0 1
0 1 1 1 0 0
  • 输出样例
1 0 1 0 0 1
1 1 0 1 0 1
0 0 1 0 1 1
1 0 0 1 0 0
0 1 0 0 0 0
  • 分析 假设当前灯亮,按钮按一次,灯变灭,再按一次,灯又变亮,恢复到了初始状态,因此,按钮按两次是没意义的。结论:按钮按偶数次没意义,按钮按奇数次与按一次一样,因此,每个按钮最多按一次。
  • 解题思路
1. 枚举所有可能的按钮状态,每种状态计算一下最后的情况,看是否都熄灭。所有状态数为2302^{30},因此这种方案不可行。
2. 如果存在某个局部,一旦这个局部的状态确定,那么剩下的其它状态只能是确定的一种,或不多的n种,则只需要枚举这个局部即可。以第一行为例,假设它就是那个局部,如果第一行的状态确定了,是不是第二行的状态就确定了呢?答案是是的,因为第一行按钮按过之后,亮的灯只有按第二行才能将其熄灭。同理,第二行按钮按下后,只能通过第三行按钮来控制灯熄灭。
3. 枚举第一行的所有可能状态,每个位置有0和1两种状态,共6个位置,因此第一行的所有可能状态为26=642^6=64种,枚举状态可以通过递归实现。如果使用每个比特位代表一个灯的话,则可能的状态为数字0-63。方法一
#!/usr/bin/env python
# _*_ coding: utf-8 _*_

import numpy as np


# 枚举第一行的所有可能状态
def all_status(status_list, status, depth):
    rows, columns = status.shape
    other = status.copy()
    other[0, depth] = 1
    if depth == columns - 1:
        status_list.append(status.copy())    
        status_list.append(other.copy())
    else:
        all_status(status_list, status.copy(), depth + 1)
        all_status(status_list, other.copy(), depth + 1)


# 如果按钮按下,更改灯的状态
def light_change(input_data, i, j):
    rows, columns = input_data.shape
    input_data[i, j] = (input_data[i, j] + 1) % 2
    if (i - 1) >= 0:
        input_data[i - 1, j] = (input_data[i - 1, j] + 1) % 2
    if (i + 1) < rows:
        input_data[i + 1, j] = (input_data[i + 1, j] + 1) % 2
    if (j - 1) >= 0:
        input_data[i, j - 1] = (input_data[i, j - 1] + 1) % 2
    if (j + 1) < columns:
        input_data[i, j + 1] = (input_data[i, j + 1] + 1) % 2



# 尝试关闭所有灯
def light_off(input_data, output_data):
    rows, columns = input_data.shape
    # 根据第一行按钮的状态修改灯的亮灭
    for i in xrange(0, columns):
        if output_data[0, i] == 1:
            light_change(input_data, 0, i)
    # 从第二行开始,每一行的按钮都使上一行的灯熄灭
    for i in xrange(1, rows):
        for j in xrange(0, columns):
            if input_data[i - 1, j] == 1:
                light_change(input_data, i, j)
                output_data[i, j] = 1
    if np.sum(input_data) == 0:
        return True, output_data
    else:
        return False, output_data

# 输出指定格式的结果
def print_result(output_data):
    rows, columns = output_data.shape
    for i in xrange(rows):
        binary_string = ''
        for j in xrange(columns):
            binary_string += str(output_data[i, j])
        print binary_string

input_list = []
input_data = np.array([[0, 1, 1, 0, 1, 0],
                       [1, 0, 0, 1, 1, 1],
                       [0, 0, 1, 0, 0, 1],
                       [1, 0, 0, 1, 0, 1],
                       [0, 1, 1, 1, 0, 0]], dtype = 'int8')
input_list.append(input_data)
input_data = np.array([[0, 0, 1, 0, 1, 0],
                       [1, 0, 1, 0, 1, 1],
                       [0, 0, 1, 0, 1, 1],
                       [1, 0, 1, 1, 0, 0],
                       [0, 1, 0, 1, 0, 0]], dtype = 'int8')
input_list.append(input_data)
status_list = []
status = np.zeros((5, 6), dtype = 'int8')
all_status(status_list, status, 0)
for i in xrange(len(input_list)):
    input_data = input_list[i]
    for j in xrange(len(status_list)):
        flag, output_data = light_off(input_data.copy(), status_list[j].copy())
        if flag:
            print j
            print 'PUZZLE #%d' % (i + 1)
            print_result(output_data)
            break
  • 结果
PUZZLE #1
101001
110101
001011
100100
010000
PUZZLE #2
100111
110000
000100
110101
101101
  • 方法二
#!/usr/bin/env python
# _*_ coding: utf-8 _*_



# 取特定位置上的比特,索引从0开始
def get_bit(number, index):
    return (number >> index) & 1


# 设定特定位置上的比特
def set_bit(number, index, value):
    return number | (value << index)


# 特定位置上的比特反转
def flip(number, index):
    return number ^ (1 << index)


# 如果按钮按下,更改灯的状态
def light_change(input_data, i, j):
    rows = 5
    columns = 6
    input_data[i] = flip(input_data[i], j)
    if (i - 1) >= 0:
        input_data[i - 1] = flip(input_data[i - 1], j)
    if (i + 1) < rows:
        input_data[i + 1] = flip(input_data[i + 1], j)
    if (j - 1) >= 0:
        input_data[i] = flip(input_data[i], j - 1)
    if (j + 1) < columns:
        input_data[i] = flip(input_data[i], j + 1)


# 尝试关闭所有灯
def light_off(input_data, output_data):
    rows = 5
    columns = 6
    # 根据第一行按钮的状态修改灯的亮灭
    for i in xrange(0, columns):
        if get_bit(output_data[0], i) == 1:
            light_change(input_data, 0, i)
    # 从第二行开始,每一行的按钮都使上一行的灯熄灭
    for i in xrange(1, rows):
        for j in xrange(0, columns):
            if get_bit(input_data[i - 1], j) == 1:
                light_change(input_data, i, j)
                output_data[i] = set_bit(output_data[i], j, 1)
    if input_data[-1] == 0:
        return True
    else:
        return False


# 输出指定格式的结果
def print_result(output_data):
    for i in xrange(len(output_data)):
        binary_string = bin(output_data[i])[2:]
        diff = 6 - len(binary_string)
        for j in xrange(diff):
            binary_string = '0' + binary_string
        print binary_string


input_list = []
input_data = [int('011010', 2), int('100111', 2), int('001001', 2), int('100101', 2), int('011100', 2)]
input_list.append(input_data)
input_data = [int('001010', 2), int('101011', 2), int('001011', 2), int('101100', 2), int('010100', 2)]
input_list.append(input_data)

for i in xrange(len(input_list)):
    input_data = input_list[i]
    for j in xrange(64):
        copy = [input_data[x] for x in xrange(len(input_data))]
        output_data = [0 for k in xrange(5)]
        output_data[0] = j
        flag = light_off(copy, output_data)
        if flag:
            print 'PUZZLE #%d' % (i + 1)
            print_result(output_data)
            break
  • 结果
PUZZLE #1
101001
110101
001011
100100
010000
PUZZLE #2
100111
110000
000100
110101
101101

总结:这个问题比较复杂,其中隐含的一点就是局部状态确定后,后面的状态都会被确定,此时需要枚举局部状态。方法一与方法二的求解思路是一样,但实现方式不一样,方法一使用Numpy来处理数据,而方法二使用比特来处理数据。

源码地址:Numpy方法二进制比特方法,记得给个star。

参考资料

  1. 程序设计与算法(二)算法基础
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2017年12月23日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 1. 枚举
  • 2. 熄灯问题(POJ1222)
  • 参考资料
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档