题目描述
小李的同事们很喜欢玩狼人杀，每次都找他当法官。小李觉得很累，决定写一个程序来跑出狼人杀的结果。
狼人杀是一个桌游。常见局由 12 名玩家和 1 名法官组成。12 名玩家坐成一个圈。每个玩家在游戏开始时随机抽取一张角色卡牌，只能知道自己的身份。 玩家分为两个阵营，狼人和村民。
- 狼人的胜利条件是 狼人阵营的玩家数 >= 村民阵营的玩家数
- 村民的胜利条件是 所有狼人出局
游戏过程
游戏分为夜晚和白天。
- (夜晚) 拿到狼人身份的玩家睁眼，其他人闭眼。狼人们商量后选择一名玩家击杀；
- (白天) 所有人睁眼；
- 法官宣布昨晚出局的玩家，以及熊是否咆哮了；
- 出局的玩家离开游戏，发动技能（如果有）；
- 法官检查胜利条件，如果任何一个满足则结束游戏；
- 在场玩家进行一轮发言，并票选最可疑的玩家出局；
- 被选中的玩家离开游戏，发动技能（如果有）；
- 法官检查胜利条件，如果任何一个满足则结束游戏；
- 重复 1；
游戏角色
【村民阵营】x8
- 村民(villager, 下称
"vil") x5：没有特殊技能 - 猎人(
"hunter") x1：技能是在出局时（被投票或被狼人击杀）可以向所有人亮出底牌选择带走一名玩家 - 白痴(
"idiot") x1：技能是在白天被投票出局后自动亮出底牌并且不出局 - 驯熊人(bear tamer, 下称
"bear") x1：（简称熊）每天夜里，如果相邻两名存活玩家有任何一个是狼人，熊会发出咆哮。如果驯熊人已经死亡，则这一局熊不再咆哮。驯熊人如果当晚被杀，熊也不会咆哮。（相邻指向左找第一名存活玩家和向右找第一名存活玩家，当晚被杀的玩家也视为死亡）
【狼人阵营】x4
- 狼人(werewolf, 下称
"ww") x4：可以知道同伴，但不知道好人的具体角色。
对于所有人：
- 白天可以投票
- 除了发言的环节，玩家不能发言或者交换信息
模拟器设定
- 我们用 c 来模拟每名玩家在游戏开始时在他人眼中的可信度。0 < c < 100 。越小则越像狼人
- 狼人只击杀非狼人，并且在场玩家知晓这点
- 在投票环节，c 最低的玩家出局。如果有多个目标，则座位号小号出局。
- 狼人优先击杀熊，其他时候击杀 c 最高的好人（村民阵营），如果有多个目标，则击杀座位号小号。
- 玩家的 c 变成 0 或者 100 表示已知身份： 铁狼 或者 铁好人
- 玩家的 c 会根据大家获取到的信息发生改变， 所有人看到的可信度 c 一起更新。注意，改变的时机需要遵守游戏过程：
- 猎人出局或白痴被投票出局时一定发动技能，使 ta 的 c 变为 100；猎人会射杀 c 最低的玩家，如果有多个目标，则射杀座位号小号
- 第一天发言时，如果驯熊人依然存活，驯熊人会公布身份，使 ta 的 c 变为 100（在模拟器中狼不会假装自己是熊）
- 如果熊咆哮了，人们开始怀疑其左右的未知身份玩家，这使他们的 c 变为原来的一半 (向下取整, 如果原来是 1 则不变 )
- 如果熊咆哮了且左右的在局一方为铁好人，则另一方成为铁狼；如果其中一方后来被发现是铁好人，人们也会更新另一方的 c
- 如果熊在场且没有咆哮，则左右的在场玩家成为铁好人
- 如果驯熊人在第一次发言前死亡，则场上玩家不知道其位置，也无法利用熊的咆哮信息
- 如果玩家在夜间死亡，则该离场的玩家也被认为是铁好人
输入：
players：一个长度为 12 的 string 数组，坐标代表座位，字符串代表底牌, 有以下可能："vil", "hunter", "idiot", "bear" 和 "ww"。 其中 "vil" 会出现 5 次， "ww"会出现 4 次， 其他每个都是 1 次。 坐标 0 和 11 也视为相邻。
credibility：一个长度为 12 的 int 数组，坐标代表座位，int 代表玩家初始的可信度
输出：
根据模拟器的设定，村民阵营是否能赢
示例 1：
Input: players = ["bear","vil","vil","ww","vil","vil","idiot","ww","hunter","ww","ww","vil"], credibility = [9,55,62,74,43,70,13,23,15,78,61,66]
Output: false解释：
第一天夜晚，狼人击杀玩家 5，熊没有咆哮。
第二天白天，玩家 0 公布自己熊的身份。玩家 1 和玩家 11 成为 铁好人。看上去最可疑的玩家 6 被投出，但是因为是 白痴 身份，并没有出局。玩家 6 成为 铁好人。
第二天夜晚，狼人击杀玩家 0 驯熊人。熊没有咆哮。
第三天白天，身份最低的玩家 8 猎人被投票出局。猎人选择带走场上可信度最低的玩家 7。
第三天夜晚，狼人击杀身份最高的玩家 1 村民。
第四天白天，身份最低的玩家 4 村民被投票出局。
第四天夜晚，狼人击杀玩家 6 白痴, 此时场上狼人数量等于好人数量，狼人胜利。
示例 2：
Input: players = ["vil", "vil", "vil", "ww", "vil", "ww", "ww", "vil", "ww", "bear", "hunter", "idiot"], credibility = [81, 71, 88, 31, 34, 40, 70, 94, 73, 79, 98, 48]
Output: true解释：
第一回合猎人出局，熊咆哮了，但由于熊没有跳身份，对于猎人是无效信息，不能更新 c ，猎人击杀 3 号位玩家狼人。本回合投票投出 11 号白痴，白痴亮出身份牌， c 变为 100 。
示例 3：
Input: players = ["vil","ww","bear","hunter","ww","idiot","vil","vil","ww","vil","ww","vil"], credibility = [45,67,32,25,1,27,99,85,3,54,3,25]
Output: true解释：
最后一轮投票，猎人被投出，发动技能。由于此时猎人已经是铁好人，通过第一轮熊咆哮可以得出 1 号位是铁狼，所以本轮猎人击杀 1 号位狼人，游戏结束，村民胜利。
题解思路
这道题是希望实现一个狼人杀的模拟器。为了简化游戏，假定每个人的可信度是公共的，狼人不自刀等等。题目并不复杂，读完题目就战胜了 99% 的玩家🤪。只是有一些细节需要注意：
- 熊的咆哮是在狼人杀人后，但是在熊发言前，场上的好人或者狼人并不知晓熊的身份
- 被熊“标记”过的玩家可能后来因为夜间死亡或者翻牌而证实身份，从而使另一方为确定的狼人
参考代码
class Solution:
def canVillagersWin(self, players, credibility):
# [角色，分数，存活态]
players = [[player, c, True] for player, c in zip(players, credibility)]
# 因为🐻只叫一次，只需要记住最多一次🐻咆哮时的疑似铁🐺
self.tielang_candidates = []
self.players = players
self.bear_index = self.get_bear_index()
self.day = 0
while True:
self.print_status()
self.day += 1
# night
# 🐺 活动
killed = self.kill()
# 死人变成铁好人
self.check_tielang(killed)
# 判断 🐻 的咆哮
left, right, roared = self.bear()
# day
# 猎人 发动技能
self.check_hunter(killed)
# 检查胜利条件
result = self.did_villagers_win()
if result is not None:
return result
# 发言，投票阶段
self.process_bear(players, left, right)
voted = self.vote(players)
# 猎人 发动技能
self.check_hunter(voted)
result = self.did_villagers_win()
if result is not None:
return result
def print_status(self):
print(f'Day {self.day}')
print(''.join(f'({ii}){a[0]:<10}' for ii, a in enumerate(self.players)))
print(''.join(f'{(str(a) + ("" if alive else "(dead)")):<13}' for _, a, alive in self.players))
def did_villagers_win(self):
# True 好人
# False 狼人
# None not yet
ww_cnt = 0
vil_cnt = 0
for player in self.players:
if self.is_dead(player):
continue
if player[0] == 'ww':
ww_cnt += 1
else:
vil_cnt += 1
if ww_cnt == 0:
print('game over! villagers win!')
return True
if ww_cnt >= vil_cnt:
print('game over! werewolves win!')
return False
def get_lowest_index(self, players):
lowest = None
for i, player in enumerate(players):
if self.is_dead(player):
# voted out
continue
if lowest is None or player[1] < players[lowest][1]:
lowest = i
return lowest
def vote(self, players):
lowest = self.get_lowest_index(players)
voted_out = players[lowest]
exempted = voted_out[0] == 'idiot'
print(f'player {lowest}[{voted_out[0]}]{" not" if exempted else ""} voted out!')
if exempted:
voted_out[1] = 100
self.check_tielang(lowest)
else:
self.set_to_dead(voted_out)
return lowest
def bear(self):
if self.is_dead(self.players[self.bear_index]):
return None, None, False
left = self.bear_index - 1
while self.is_dead(self.players[left]):
left -= 1
if left < 0:
left += len(self.players)
right = (self.bear_index + 1) % len(self.players)
while self.is_dead(self.players[right]):
right = (right + 1) % len(self.players)
left_p = self.players[left]
right_p = self.players[right]
roared = left_p[0] == 'ww' or right_p[0] == 'ww'
if roared:
self.tielang_candidates = [left, right]
return left, right, roared
def process_bear(self, players, left, right):
# 发言阶段
if self.is_dead(players[self.bear_index]):
return
players[self.bear_index][1] = 100
left_p = players[left]
right_p = players[right]
left_dead = self.is_dead(left_p)
right_dead = self.is_dead(right_p)
print(f'left {left}{" dead" if left_dead else ""}, right {right}{" dead" if right_dead else ""}')
if left_p[0] == 'ww' or right_p[0] == 'ww':
if 1 < left_p[1] < 100 and not left_dead:
left_p[1] //= 2
if 1 < right_p[1] < 100 and not right_dead:
right_p[1] //= 2
if left_p[1] == 100 and not right_dead:
# 铁狼！
right_p[1] = 0
elif right_p[1] == 100 and not left_dead:
# 铁狼！
left_p[1] = 0
print('roar~~~')
else:
left_p[1] = 100
right_p[1] = 100
print(f'{left}, {right} 金水')
def kill(self):
player_no = self.bear_index
# 🐺 已知 🐻 的位置
if not self.is_dead(self.players[player_no]) and self.players[player_no][1] == 100:
player_to_kill = self.players[player_no]
else:
player_to_kill = None
for i, player in enumerate(self.players):
if self.is_dead(player) or player[0] == 'ww':
continue
if player_to_kill is None or player[1] > player_to_kill[1]:
player_to_kill = player
player_no = i
self.set_to_dead(player_to_kill)
print(f'player {player_no}[{player_to_kill[0]}] killed')
return player_no
def check_hunter(self, num):
if self.players[num][0] == 'hunter':
self.check_tielang(num)
lowest = self.get_lowest_index(self.players)
self.set_to_dead(self.players[lowest])
print(f'hunter shoot {lowest}[{self.players[lowest][0]}]')
return lowest
return None
def get_bear_index(self):
for i, p in enumerate(self.players):
if p[0] == 'bear':
return i
def is_dead(self, player):
return not player[2]
def set_to_dead(self, player):
player[2] = False
def check_tielang(self, player_no: int):
if self.tielang_candidates and self.players[self.bear_index][1] == 100:
try:
self.tielang_candidates.remove(player_no)
except ValueError:
pass
else:
# 铁狼
tielang = self.tielang_candidates[0]
if not self.is_dead(self.players[tielang]):
self.players[tielang][1] = 0
print(f'铁狼 {tielang} from {player_no}')
self.tielang_candidates = []
评论 (5)
