【蓝桥杯】43697.机器人塔

题目描述

X 星球的机器人表演拉拉队有两种服装，A 和 B。

他们这次表演的是搭机器人塔。

类似：

B B

A B A

A A B B

B B B A B

A B A B B A

队内的组塔规则是：

A 只能站在 AA 或 BB 的肩上。

B 只能站在 AB 或 BA 的肩上。

你的任务是帮助拉拉队计算一下，在给定 A 与 B 的人数时，可以组成多少种花样的塔。

输入描述

输入一行两个整数 M,N（0<M,N<500）,分别表示 A、B 的人数，保证人数合理性。

输出描述

要求输出一个整数，表示可以产生的花样种数。

输入输出样例

示例
输入

1 2

输出

3

题目解析

通读一遍题目，已知“初始局面”，求“未来可能的局面”的数量，不出意外的话，这又是一道关于“遍历”类型的题目，那么我们首先会考虑到深度优先搜索DFS 或者广度优先搜索BFS 算法。

比如说，有一个A，两个B，那么有多少种组合方式呢？
看下规则的说明：

A 只能站在 AA 或 BB 的肩上。
B 只能站在 AB 或 BA 的肩上。

在这个案例中，有一个A和两个B，先从A开始遍历。
如果第一行是A，那么在剩下的字符中，第二行只有BB这一种组合；
A
B B
如果第一行是B，那么在剩下的字符中，第二行可以有AB或者BA这两种组合；
B 或者 B
A B B A
那么一共有3种组合的可能性局面。

在这其中有一个重要的规律：如果底层相邻的两个字符相同（比如都是AA或BB），则上层对应的一定是A；如果底层相邻的两个字符不同（比如是AB或BA），则上层对应的一定是B。

使用DFS算法解决该问题，算法的核心目标是根据输入的 A 和 B 的数量，找出所有可能的机器人塔花样。其步骤包括：计算塔的层数、使用深度优先搜索生成所有可能的底层排列、对每个底层排列检查是否能构建出满足规则且 A、B 数量符合要求的塔，最后输出符合条件的塔的数量。

算法步骤

读取输入
在 main 函数中，首先通过 map(int, input().split()) 读取用户输入的一行两个整数，分别赋值给变量 m 和 n，它们分别代表 A 和 B 的数量。
计算塔的层数
根据机器人塔的结构特点，总的机器人数等于从 1 到塔层数的连续整数之和，即满足公式 total = layer * (layer + 1) // 2，其中 total = m + n。通过一个循环不断增加 layer 的值，直到找到满足该公式的层数。
深度优先搜索
调用 dfs 函数开始深度优先搜索，初始参数为当前层（初始设为 1）、目标底层长度（即上面计算得到的塔的层数 layer）、A 和 B 的目标数量 m 和 n，以及一个空列表表示初始的底层排列。
终止条件判断：当当前正在构建的底层排列 current_bottom 的长度达到目标底层长度 target_layer 时，说明已经生成了一个完整的底层排列。此时调用 check_tower 函数检查该底层排列是否能构建出满足条件的塔，如果满足则将全局结果计数器 result 加 1。
递归搜索：如果底层排列还未构建完成，则分别尝试在 current_bottom 后面添加 ‘A’ 和 ‘B’，并递归调用 dfs 函数继续生成底层排列。
检查塔是否满足条件
构建塔：从给定的底层排列 bottom 开始，根据组塔规则逐层向上构建塔。对于每一层，根据相邻两个元素的情况生成上一层的元素：如果相邻两个元素相同则生成 ‘A’，不同则生成 ‘B’。
统计 A 和 B 的数量：遍历整个塔的每一层，统计其中 A 和 B 的数量。
判断是否满足条件：最后判断统计得到的 A 和 B 的数量是否与目标数量 m 和 n 相等，如果相等则返回 True，表示该底层排列能构建出满足条件的塔，否则返回 False。
输出统计结果

代码实现

DFS 调用实现

python"># 全局变量用于存储最终结果
result = 0

# 深度优先搜索函数，生成底层排列并检查是否满足条件
def dfs(current_layer, target_layer, m, n, current_bottom):
    global result
    # 当生成的底层排列达到目标长度时
    if len(current_bottom) == target_layer:
        # 调用检查函数判断是否满足条件
        if check_tower(current_bottom, m, n):
            result += 1
        return
    # 尝试添加 'A' 到当前底层排列
    dfs(current_layer, target_layer, m, n, current_bottom + ['A'])
    # 尝试添加 'B' 到当前底层排列
    dfs(current_layer, target_layer, m, n, current_bottom + ['B'])

# 检查基于给定底层排列构建的塔是否满足 A 和 B 的数量要求
def check_tower(bottom, m, n):
    tower = [bottom]
    current = bottom
    # 逐层向上构建塔
    while len(current) > 1:
        next_layer = []
        for i in range(len(current) - 1):
            if current[i] == current[i + 1]:
                next_layer.append('A')
            else:
                next_layer.append('B')
        tower.append(next_layer)
        current = next_layer
    # 统计塔中 A 和 B 的数量
    count_a = 0
    count_b = 0
    for layer in tower:
        count_a += layer.count('A')
        count_b += layer.count('B')
    # 判断数量是否与目标一致
    return count_a == m and count_b == n

# 主函数，读取输入并启动深度优先搜索
def main():
    global result
    m, n = map(int, input().split())
    total = m + n
    layer = 1
    # 计算塔的层数
    while layer * (layer + 1) // 2 != total:
        layer += 1
    # 启动深度优先搜索
    dfs(1, layer, m, n, [])
    print(result)

if __name__ == "__main__":
    main()

非DFS算法

python"># 检查一个可能的底层排列是否能组成满足规则的塔
def check_bottom(bottom, m, n):
    tower = [bottom]
    current = bottom
    # 逐层构建塔
    while len(current) > 1:
        next_layer = []
        for i in range(len(current) - 1):
            if current[i] == current[i + 1]:
                next_layer.append('A')
            else:
                next_layer.append('B')
        tower.append(next_layer)
        current = next_layer
    # 统计 A 和 B 的数量
    count_a = 0
    count_b = 0
    for layer in tower:
        count_a += layer.count('A')
        count_b += layer.count('B')
    return count_a == m and count_b == n

# 生成所有可能的底层排列
def generate_bottoms(length):
    from itertools import product
    return product(['A', 'B'], repeat=length)

# 主函数
def main():
    m, n = map(int, input().split())
    # 计算塔的层数
    total = m + n
    layer = 1
    while layer * (layer + 1) // 2 != total:
        layer += 1
    # 生成所有可能的底层排列
    bottoms = generate_bottoms(layer)
    # 检查每个底层排列是否满足条件
    result = 0
    for bottom in bottoms:
        if check_bottom(list(bottom), m, n):
            result += 1
    print(result)

if __name__ == "__main__":
    main()