首先猫和老鼠的游戏是在一张无向图上进行的,题目中说图的形式是:graph[a] 是一个列表,由满足 ab 是图中的一条边的所有节点 b 组成。我们就从输入的graph列表入手,来看下这个列表是如何表示示例1中的无向图的。
graph = [[2,5],[3],[0,4,5],[1,4,5],[2,3],[0,2,3]],我们把列表的下标当作第i个节点,那么0号节点与2、5直接相连;1号只与3直接相连;2号能直接到达0、4、5;3号直接到达1、4、5……以此类推,我们把对应节点所能直接到达的所有节点放在列表中,发现正是得到了graph这个列表。
在猫和老鼠游戏中有三种情况:
1、老鼠进洞x=0,老鼠赢return 1
2、猫捉住老鼠x=y,猫赢return 2
3、假设走n步有一方一定获得胜利,由于题目中说了猫和老鼠都是采取最优解,“假设两位玩家都都以最佳状态参与游戏”,那么如果达到2n还没有分出胜负(转了一圈还没抓住,这里其实大于n即可满足平局条件)则判为平局。
用t表示步数,x表示老鼠的位置,y表示猫的位置;用x_next和y_next分别表示老鼠和猫的下一步,如果下一步出现x=0则老鼠赢,如果x=y则猫赢,否则平局,对于猫可移动位置需要去除老鼠洞,即y_next!=0;由于第一步是老鼠先走,那么当步数为偶数时,下一步一定是轮到老鼠走,即t%2==0。
另外对于老鼠来说首先接受老鼠胜利,其次是平局,对于猫是接受猫胜利,其次平局。这里用了lru_cache做了记忆化。
from typing import List
from functools import lru_cache
def catMouseGame(graph: List[List[int]]) -> int:
M_WIN = 1 # 老鼠赢
C_WIN = 2 # 猫赢
PEACE = 0 # 平局
@lru_cache(None)
def search(t, x, y):
if x == 0: # 老鼠进洞,老鼠获胜
return M_WIN
if x == y: # 猫捉住鼠,猫获胜
return C_WIN
if t == int(2 * len(graph)): # 如果步数为2n(大于n),即为平局
return PEACE
if t % 2 == 0: # 下一步是老鼠走,如果能进洞,则老鼠赢
if any(search(t + 1, x_next, y) == M_WIN for x_next in graph[x]): # 当前节点可达的下一个节点
return M_WIN
if any(search(t + 1, x_next, y) == PEACE for x_next in graph[x]):
return PEACE
return C_WIN
else: # 下一步是猫走,如果捉住老鼠,则猫赢
if any(search(t + 1, x, y_next) == C_WIN for y_next in graph[y] if y_next!=0):
return C_WIN
if any(search(t + 1, x, y_next) == PEACE for y_next in graph[y] if y_next!=0):
return PEACE
return M_WIN
return search(0, 1, 2) # 初始状态
graph = [[2, 5], [3], [0, 4, 5], [1, 4, 5], [2, 3], [0, 2, 3]]
print(catMouseGame(graph)) # 0
END