教科书般的亵渎

发表于 更新于 分类于 阅读次数： Valine：
本文字数： 2.1k 阅读时长 ≈ 2 分钟

教科书般的亵渎

背景介绍

炉石传说里术士有一张非常强力的AOE卡牌“亵渎”

xiedu

这张牌的效果是：对所有随从造成1点伤害，如果有随从死亡，则再次施放该法术。

在经过仔细地计算之后，即使是非常复杂的场面，也可能通过随从相互进行攻击，构造血量的等差数列，然后使用2费的亵渎达到清场。但在一个回合有限的思考时间里，这“高等术学”并不是那么容易计算出来的。

亵渎计算器

在编写亵渎计算器之前，先把这个问题描述清楚：

输入：给定敌方和我方不多于7个随从的攻击力、生命值、是否具有嘲讽、我方该随从本回合是否能进行攻击（暂时不考虑亡语、圣盾、风怒、复生等复杂的效果）

输出：所有全清场面的我方随从攻击方案

下面用Python3.7来实现：

先写一些测试用例和全局变量

1
2
3
4
5
6
7
8
9
10
11
12
a2 = [1, 2, 3] # 敌方随从攻击力
h2 = [2, 4, 4] # 敌方随从生命值
taunt = [0, 1, 0] # 敌方随从是否具有嘲讽

a1 = [1, 1] # 我方随从攻击力
h1 = [1, 2] # 我方随从生命值

flag = False # 是否有解
attack_record = [] # 用一个栈记录攻击
H1 = h1[:]
H2 = h2[:]
num_of_solutions = 0

然后写一个判断等差数列的函数，h1和h2是存储敌方和我方随从生命值的列表，判断是否构成等差数列

1
2
3
4
5
6
def is_AP(h1, h2):
    maxH = max(max(h1), max(h2))
    for i in range(1, maxH):
        if i not in h1 and i not in h2:
            return False
    return True

再写一个主函数，如果初始就构成了等差数列就直接输出，不进行DFS；如果不构成等差数列，则进行DFS

1
2
3
4
5
6
7
8
9
10
11
12
def main():
    num_of_taunt = sum(taunt)
    if is_AP(H1, H2):
        print(attack_record)
        print(H2)
        print(H1)
        print("number of solutions: 1" )
    else:
        DFS(0, 0, num_of_taunt)
        if flag == False:
            print("No Solution.")
        print("number of solutions: " + str(num_of_solutions))

然后是DFS的实现：

这里需要传入的参数有三个，k1和k2分别代表我方和敌方的随从序号，num_of_taunt是敌方场上嘲讽随从的数量（这个会影响是否能进行攻击所以要记录）

分支分为两类：我方k1攻击敌方k2，我方k1不攻击敌方k2

攻击分支：根据两个随从的生命值以及场上嘲讽的情况来进行剪枝

不攻击分支：要根据是否还有下一个敌方随从来进行判断

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def DFS(k1, k2, num_of_taunt):
    # 已经构成等差数列
    if is_AP(H1, H2):
        global flag
        flag = True # 有解
        global num_of_solutions
        num_of_solutions = num_of_solutions + 1

        print(attack_record)
        print(H2)
        print(H1)
        print('\n')

    # 递归边界
    if k1 >= len(H1):
        return
    
    # k1撞k2
    if H1[k1] >= 0 and H2[k2] >= 0: # 生命值不为负才能攻击
        if num_of_taunt == 0 or taunt[k2]: # 没有嘲讽随从或k2是嘲讽随从
            attack(k1, k2, num_of_taunt)

    # k1不撞k2
    if k2+1 < len(H2): # 还有下一个敌方随从
        DFS(k1, k2+1, num_of_taunt)
    elif k1+1 < len(H1): # 没有下一个敌方随从
        DFS(k1+1, 0, num_of_taunt)

最后是攻击分支的具体实现：需要判断攻击之后是否会对敌方嘲讽状况发生影响

1
2
3
4
5
6
7
8
9
10
11
def attack(k1, k2, num_of_taunt):
    H1[k1] = H1[k1] - a2[k2]
    H2[k2] = H2[k2] - a1[k1]
    attack_record.append(str(k1) + " attack " + str(k2))
    if taunt[k2] and H2[k2] <= 0:
        DFS(k1+1, 0, num_of_taunt - 1)
    else:
        DFS(k1+1, 0, num_of_taunt)
    attack_record.pop(-1)
    H1[k1] = H1[k1] + a2[k2]
    H2[k2] = H2[k2] + a1[k1]

程序输出如下：

1
2
3
4
5
6
['1 attack 1']
[2, 3, 4]
[1, 0]


number of solutions: 1

敌方1号随从嘲讽，容易验证的确只有这一个解：我方1号随从攻击敌方1号随从，然后使用亵渎全解

第二、三行输出显示亵渎前敌方和我方随从剩余生命值，的确构成等差数列

相关文章