一道智力题

最近在同学的 QQ 空间上,发现了这样一道智力题:

有一条河,河边有一个猎人牵着一头狼,一个男人带着两个小男孩,还有一个女人带着两个小女孩。
如果猎人离开,狼就会把所有人吃掉。
如果男人离开,女人会把两个小男孩掐死。
如果女人离开,男人会把两个小女孩掐死。
河里有一条船,船上只能乘坐两人(狼算一人),只有猎人、男人、女人会划船。
如何使他们全部过河?

看到这道题,首先想到的是农夫过河问题。既然这两个问题十分相似,那我就尝试按照农夫过河问题的思路,通过程序来找出该题的解。

程序代码如下:

#!/usr/local/bin/python3
##########################################
# 问题:
# 有一条河,河边有一个猎人牵着一头狼,一个男人带着两个小男孩,还有一个女人带着两个小女孩
# 如果猎人离开,狼就会把所有人吃掉
# 如果男人离开,女人会把两个小男孩掐死
# 如果女人离开,男人会把两个小女孩掐死
# 河里有一条船,船上只能乘坐两人(狼算一人),只有猎人、男人、女人会划船
# 如何使他们全部过河?


##########################################
# 思路:
# 与农夫过河问题类似,参考 https://www.zhihu.com/question/29968331
# 一共有 8 个人(包含狼),每个人有两个状态:分别为在河的一侧,以及在河的另一侧
# 这两种状态可用一个二进制位表示,0 代表在河的一侧,1 代表在河的另一侧
# 则可用一个 8 位二进制数表示这 8 个人的状态,进行组合,一共有 256 个状态
# 通过坐船,可以使一种状态转变为另一种状态
# 如果状态从 00000000 转换到 11111111, 则说明所有人均到达河的另一侧 
# 将两种可以相互转变的状态相互连接,可以构建出一个用于表示状态转移情况的图
# 在图中找到一条从 00000000 到 11111111 的路径,即可解决该问题


##########################################
# 数据存储格式:
# 使用 8 位二进制数进行表示,从高位到低位分别表示男人,男孩,男孩,女人,女孩,女孩,狼的状态 


# 船允许的所有状态,1 代表在船上
# 将两个状态进行异或操作,发生变化的位就会置一,则说明置一的位所对应的人是在船上
# 但是,船的行驶是有方向的,例如从 10000000 到 01000000 的状态是无法通过一次乘船达到的
# 所以需要进行进一步判断,具体方法见下面的代码
boatAllowedStates = [
    0b11000000, 0b10100000, 0b00011000, 0b00010100, 0b10000010,
    0b01000010, 0b00100010, 0b00010010, 0b00001010, 0b00000110,
    0b00000011, 0b10010000, 0b10000000, 0b00010000, 0b00000010
]

# 以邻接矩阵的形式存储可能的状态转移情况
# 矩阵的索引就是用于表示状态的 8 位二进制数(0~255)
statesGraph = [([0] * 256) for i in range(256)] # 创建 256x256 二维数组

# 判断是否为危险的状态
def is_dangerous(x):
    # 第一种不安全的情况:男人不在,女人在,男孩在
    if ( x & 0b10000000) == 0 and ( x & 0b00010000) != 0 and ( x & 0b01100000) != 0:
        return True
    if (~x & 0b10000000) == 0 and (~x & 0b00010000) != 0 and (~x & 0b01100000) != 0:
        return True
    # 第二种不安全的情况:女人不在,男人在,女孩在
    if ( x & 0b00010000) == 0 and ( x & 0b10000000) != 0 and ( x & 0b00001100) != 0:
        return True
    if (~x & 0b00010000) == 0 and (~x & 0b10000000) != 0 and (~x & 0b00001100) != 0:
        return True
    # 第三种不安全的情况:猎人不在,狼在,其他人在
    if ( x & 0b00000010) == 0 and ( x & 0b00000001) != 0 and ( x & 0b11111100) != 0:
        return True
    if (~x & 0b00000010) == 0 and (~x & 0b00000001) != 0 and (~x & 0b11111100) != 0:
        return True
    return False

# 构建该邻接矩阵
for x in range(0, 256):
    if is_dangerous(x):      # 判断 x 的状态是否危险 
        continue 
    for y in range(0, 256):
        if is_dangerous(y):  # 判断 y 的状态是否危险
            continue
        # 如果通过坐船,可以使状态 x 转变为状态 y, 则使矩阵对应位置为 1
        tmp = x ^ y
        if tmp in boatAllowedStates: 
            # 进一步判断,排除类似 10000000 到 01000000 的情况
            if tmp & x ^ tmp == 0 or tmp & x ^ tmp == tmp:
                statesGraph[x][y] = 1    # 连接图中能够能够转换的状态

# 通过图的深度优先搜索算法,找出一条从 0b00000000 到 0b11111111 的路径
# ⚠️TODO: 
# 此时仅仅是找到了一条能够到达的路径,不一定是最佳的结果
# 可考虑直接找出所有可行的结果
# 或使用最短路径算法,找出乘船次数最少的结果
visited = [0] * 256 # 用在图的深度优先搜索中,已访问的状态
path = [257] * 256  # 用于存储路径,数组内元素为下一个状态, 257 代表尚未初始化

def dfs_with_path(src):
    visited[src] = 1
    for i in range(0, 256):
        if statesGraph[src][i] == 1 and visited[i] == 0 and visited[0b11111111] == 0:
            path[src] = i
            dfs_with_path(i)

dfs_with_path(0b00000000)

# 将路径显示在屏幕上
tmp_path = 0
while tmp_path != 0b11111111:
    print('{0:08b}'.format(tmp_path))
    tmp_path = path[tmp_path]
    if(tmp_path == 257):
        # 257 在本程序中代表未初始化的值,如果遇到 257,说明没找到这样的路径
        print("Not found!")
        exit()
print('{0:08b}'.format(0b11111111))
print("Found!")

发表评论

电子邮件地址不会被公开。 必填项已用*标注