问题如下:
两名玩家持有以下格式的牌: 1.第一位玩家的卡片顶部有一个字母 [A-Z],底部有 1 或 2 个字母 2.第二个玩家的牌上面有一个字母[A-Z],下面有一个数字
打牌时,牌顶的字母会被底端的字母替换。
给定一个数字序列和一张最初打出的牌,两名玩家必须替换字母,直到第一张打出的牌中的字母转换为给定的序列。 两名玩家可以各自使用任意数量的牌,出牌顺序没有限制。
例子:
Player one has cards: (A, BC), (B, F), (F, BF), (C, D)
Player two has cards: (F, 0), (D, 3), (B, 2), (B, 1), (R, 3)
The given sequence: (3, 2, 0)
The initial card played: (A, BC)
1.(A, BC) played: BC
2.(C, D) played: BD
3.(D, 3) played: B (3)
4.(B, F) played: F (3)
5.(F, BF) played: BF (3)
6.(B, 2) played: F (3, 2)
7.(F, 0) played: (3, 2, 0)
我想过回溯方法,但有人告诉我不需要这样的方法,而且我想不出正确的方法
最佳答案
首先,几点观察:
The two players can use as many cards of each and there is no restriction on the order of who plays the cards.
所以这意味着实际上我们有两个玩家并不重要——重要的是游戏中有哪些牌。
此外,如果卡片有无限用途,使用字母->数字和字母->字母卡片,我们可以创建一个数字的逆向映射到指向该数字的字母列表。
完成这些步骤后,如果 <number of letters played>=<number of required numbers>
, 它看起来像一个 assignment problem .
否则(如果 <number of letters played> < <number of required numbers>
)我认为它可以通过更复杂的 flow network 来解决.
关于algorithm - 需要一些卡片替换算法的想法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/40407602/