首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >菜鸟的每日力扣系列——913. 猫和老鼠

菜鸟的每日力扣系列——913. 猫和老鼠

作者头像
才浅Coding攻略
发布于 2022-12-12 09:32:51
发布于 2022-12-12 09:32:51
27200
代码可运行
举报
文章被收录于专栏:才浅coding攻略才浅coding攻略
运行总次数:0
代码可运行

首先猫和老鼠的游戏是在一张无向图上进行的,题目中说图的形式是: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做了记忆化。

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
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

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2022-01-05,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 才浅coding攻略 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档