首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >golang刷leetcode:猫和老鼠

golang刷leetcode:猫和老鼠

作者头像
golangLeetcode
发布于 2022-08-02 11:45:18
发布于 2022-08-02 11:45:18
27900
代码可运行
举报
运行总次数:0
代码可运行

两位玩家分别扮演猫和老鼠,在一张 无向 图上进行游戏,两人轮流行动。

图的形式是:graph[a] 是一个列表,由满足 ab 是图中的一条边的所有节点 b 组成。

老鼠从节点 1 开始,第一个出发;猫从节点 2 开始,第二个出发。在节点 0 处有一个洞。

在每个玩家的行动中,他们 必须 沿着图中与所在当前位置连通的一条边移动。例如,如果老鼠在节点 1 ,那么它必须移动到 graph[1] 中的任一节点。

此外,猫无法移动到洞中(节点 0)。

然后,游戏在出现以下三种情形之一时结束:

如果猫和老鼠出现在同一个节点,猫获胜。

如果老鼠到达洞中,老鼠获胜。

如果某一位置重复出现(即,玩家的位置和移动顺序都与上一次行动相同),游戏平局。

给你一张图 graph ,并假设两位玩家都都以最佳状态参与游戏:

如果老鼠获胜,则返回 1;

如果猫获胜,则返回 2;

如果平局,则返回 0 。

示例 1:

输入:graph = [[2,5],[3],[0,4,5],[1,4,5],[2,3],[0,2,3]]

输出:0

示例 2:

输入:graph = [[1,3],[0],[3],[0,2]]

输出:1

提示:

3 <= graph.length <= 50

1 <= graph[i].length < graph.length

0 <= graph[i][j] < graph.length

graph[i][j] != i

graph[i] 互不相同

猫和老鼠在游戏中总是移动

解题思路:

这道题是博弈问题,猫和老鼠都按照最优策略参与游戏。

在阐述具体解法之前,首先介绍博弈问题中的三个概念:必胜状态、必败状态与必和状态。

对于特定状态,如果游戏已经结束,则根据结束时的状态决定必胜状态、必败状态与必和状态。

如果分出胜负,则该特定状态对于获胜方为必胜状态,对于落败方为必败状态。

如果是平局,则该特定状态对于双方都为必和状态。

从特定状态开始,如果存在一种操作将状态变成必败状态,则当前玩家可以选择该操作,将必败状态留给对方玩家,因此该特定状态对于当前玩家为必胜状态。

从特定状态开始,如果所有操作都会将状态变成必胜状态,则无论当前玩家选择哪种操作,都会将必胜状态留给对方玩家,因此该特定状态对于当前玩家为必败状态。

从特定状态开始,如果任何操作都不能将状态变成必败状态,但是存在一种操作将状态变成必和状态,则当前玩家可以选择该操作,将必和状态留给对方玩家,因此该特定状态对于双方玩家都为必和状态。

对于每个玩家,最优策略如下:

争取将必胜状态留给自己,将必败状态留给对方玩家。

在自己无法到达必胜状态的情况下,争取将必和状态留给自己。

方法一:动态规划

博弈问题通常可以使用动态规划求解。

使用三维数组 \textit{dp}dp 表示状态,\textit{dp}[\textit{mouse}][\textit{cat}][\textit{turns}]dp[mouse][cat][turns] 表示从老鼠位于节点 \textit{mouse}mouse、猫位于节点 \textit{cat}cat、游戏已经进行了 \textit{turns}turns 轮的状态开始,猫和老鼠都按照最优策略的情况下的游戏结果。假设图中的节点数是 nn,则有 0 \le \textit{mouse}, \textit{cat} < n0≤mouse,cat<n。

由于游戏的初始状态是老鼠位于节点 11,猫位于节点 22,因此 \textit{dp}[1][2][0]dp[1][2][0] 为从初始状态开始的游戏结果。

动态规划的边界条件为可以直接得到游戏结果的状态,包括以下三种状态:

如果 \textit{mouse} = 0mouse=0,老鼠躲入洞里,则老鼠获胜,因此对于任意 \textit{cat}cat 和 \textit{turns}turns 都有 \textit{dp}[0][\textit{cat}][\textit{turns}] = 1dp[0][cat][turns]=1,该状态为老鼠的必胜状态,猫的必败状态。

如果 \textit{cat} = \textit{mouse}cat=mouse,猫和老鼠占据相同的节点,则猫获胜,因此当 \textit{cat} = \textit{mouse}cat=mouse 时,对于任意 \textit{mouse}mouse、\textit{cat}cat 和 \textit{turns}turns 都有 \textit{dp}[\textit{mouse}][\textit{cat}][\textit{turns}] = 2dp[mouse][cat][turns]=2,该状态为老鼠的必败状态,猫的必胜状态。注意猫不能移动到节点 00,因此当 \textit{mouse} = 0mouse=0 时,一定有 \textit{cat} \ne \textit{mouse}cat

=mouse。

如果 \textit{turns} \ge 2nturns≥2n,则是平局,该状态为双方的必和状态。

为什么当 \textit{turns} \ge 2nturns≥2n 时,游戏结果是平局呢?

如果游戏已经进行了 2n2n 轮,但是仍然没有任何一方获胜,此时猫和老鼠各移动了 nn 次,该移动次数等于图中的节点数,因此一定存在一个老鼠到达过至少两次的节点,以及一定存在一个猫到达过至少两次的节点。

对于老鼠而言,即使按照最优策略,也无法躲入洞内,而是只能回到一个已经到达过的节点。当老鼠回到一个在过去的某个回合已经到达过的节点时,猫可能回到在相同回合已经到达过的节点,也可能移动到一个更有利于猫获胜的节点,不可能移动到一个更有利于老鼠获胜的节点(否则猫就不是按照最优策略参与游戏)。如果猫回到在相同回合已经到达过的节点,则形成循环,因此是平局;如果猫移动到一个更有利于猫获胜的节点,则老鼠的获胜机会更小,因此老鼠无法获胜。

同理可知,如果猫按照最优策略也只能回到一个已经到达过的节点,则猫无法获胜。

因此当猫和老鼠分别回到一个已经到达过的节点时,猫和老鼠都无法获胜,游戏结果是平局。

动态规划的状态转移需要考虑当前玩家所有可能的移动,选择最优策略的移动。

由于老鼠先开始移动,猫后开始移动,因此可以根据游戏已经进行的轮数 \textit{turns}turns 的奇偶性决定当前轮到的玩家,当 \textit{turns}turns 是偶数时轮到老鼠移动,当 \textit{turns}turns 是奇数时轮到猫移动。

如果轮到老鼠移动,则对于老鼠从当前节点移动一次之后可能到达的每个节点,进行如下操作:

如果存在一个节点,老鼠到达该节点之后,老鼠可以获胜,则老鼠到达该节点之后的状态为老鼠的必胜状态,猫的必败状态,因此在老鼠移动之前的当前状态为老鼠的必胜状态。

如果老鼠到达任何节点之后的状态都不是老鼠的必胜状态,但是存在一个节点,老鼠到达该节点之后,结果是平局,则老鼠到达该节点之后的状态为双方的必和状态,因此在老鼠移动之前的当前状态为双方的必和状态。

如果老鼠到达任何节点之后的状态都不是老鼠的必胜状态或必和状态,则老鼠到达任何节点之后的状态都为老鼠的必败状态,猫的必胜状态,因此在老鼠移动之前的当前状态为老鼠的必败状态。

如果轮到猫移动,则对于猫从当前节点移动一次之后可能到达的每个节点,进行如下操作:

如果存在一个节点,猫到达该节点之后,猫可以获胜,则猫到达该节点之后的状态为猫的必胜状态,老鼠的必败状态,因此在猫移动之前的当前状态为猫的必胜状态。

如果猫到达任何节点之后的状态都不是猫的必胜状态,但是存在一个节点,猫到达该节点之后,结果是平局,则猫到达该节点之后的状态为双方的必和状态,因此在猫移动之前的当前状态为双方的必和状态。

如果猫到达任何节点之后的状态都不是猫的必胜状态或必和状态,则猫到达任何节点之后的状态都为猫的必败状态,老鼠的必胜状态,因此在猫移动之前的当前状态为猫的必败状态。

实现方面,由于双方移动的策略相似,因此可以使用一个函数实现移动策略,根据游戏已经进行的轮数的奇偶性决定当前轮到的玩家。对于特定玩家的移动,实现方法如下:

如果当前玩家存在一种移动方法到达非必败状态,则用该状态更新游戏结果。

如果该移动方法到达必胜状态,则将当前状态(移动前的状态)设为必胜状态,结束遍历其他可能的移动。

如果该移动方法到达必和状态,则将当前状态(移动前的状态)设为必和状态,继续遍历其他可能的移动,因为可能存在到达必胜状态的移动方法。

如果当前玩家的任何移动方法都到达必败状态,则将当前状态(移动前的状态)设为必败状态。

特别地,如果当前玩家是猫,则不能移动到节点 00

代码实现:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
const (
    draw     = 0
    mouseWin = 1
    catWin   = 2
)

func catMouseGame(graph [][]int) int {
    n := len(graph)
    dp := make([][][]int, n)
    for i := range dp {
        dp[i] = make([][]int, n)
        for j := range dp[i] {
            dp[i][j] = make([]int, n*2)
            for k := range dp[i][j] {
                dp[i][j][k] = -1
            }
        }
    }

    var getResult, getNextResult func(int, int, int) int
    getResult = func(mouse, cat, turns int) int {
        if turns == n*2 {
            return draw
        }
        res := dp[mouse][cat][turns]
        if res != -1 {
            return res
        }
        if mouse == 0 {
            res = mouseWin
        } else if cat == mouse {
            res = catWin
        } else {
            res = getNextResult(mouse, cat, turns)
        }
        dp[mouse][cat][turns] = res
        return res
    }
    getNextResult = func(mouse, cat, turns int) int {
        curMove := mouse
        if turns%2 == 1 {
            curMove = cat
        }
        defaultRes := mouseWin
        if curMove == mouse {
            defaultRes = catWin
        }
        res := defaultRes
        for _, next := range graph[curMove] {
            if curMove == cat && next == 0 {
                continue
            }
            nextMouse, nextCat := mouse, cat
            if curMove == mouse {
                nextMouse = next
            } else if curMove == cat {
                nextCat = next
            }
            nextRes := getResult(nextMouse, nextCat, turns+1)
            if nextRes != defaultRes {
                res = nextRes
                if res != draw {
                    break
                }
            }
        }
        return res
    }
    return getResult(1, 2, 0)
}
本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2022-05-03,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 golang算法架构leetcode技术php 微信公众号,前往查看

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

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

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
C嘎嘎入门篇:类和对象(1)
小编在之前讲述了C++的部分入门基础,读者朋友一定要掌握好那些,因为C++的学习和C有点不同,C++的知识都是比较连贯的,所以我们学好了前面才可以学习后面的内容,本篇文章小编将会讲述C++真正的入门篇:类和对象,学完这一部分后我们才可以说我们真的C++入门了,下面废话不多说,开启今天第一部分的讲解:
用户11295429
2024/10/16
1020
C嘎嘎入门篇:类和对象(1)
python入门教程NO.9 怎么理解面向对象编程?看我就够了!
在python中,用变量表示属性,用函数表示方法,因此具有相同属性和方法的一类事物就是‘类’,对象就是这这类事物中具体的一个。
python鱼霸霸
2020/04/23
4300
1.面向对象:初识
面向对象的程序设计的核心是对象(上帝式思维),要理解对象为何物,必须把自己当成上帝,上帝眼里世间存在的万物皆为对象,不存在的也可以创造出来。
changxin7
2019/08/14
3070
初识Python面向对象
对象具有的行为(动词),通常可以定义成 方法(用类去定义的的对象所具备的可操作的能力叫做方法)
星陨1357
2023/03/14
2090
初识Python面向对象
【C++入门篇】保姆级教程篇【中】
由上一篇的博客我们已经学习到可以写出的基本C++程序了,接下来我们将要进入C++重要的一环——面向对象,在学习面向对象之前,我觉得有必要先了解一下面向对象的由来,那么我们就从语言的发展史开始今天的学习之旅吧!
用户11029129
2024/06/04
1360
【C++入门篇】保姆级教程篇【中】
【C++】踏上C++的学习之旅(六):深入“类和对象“世界,掌握编程的黄金法则(一)
在本文中我们即将要接触到C++的第一块"硬骨头"——“类和对象”。为什么说"类和对象"是一块一骨头呢?因为里面涉及的语法细节十分的繁杂,不过读者们不必担心,我的"类和对象"这个系列会罗列和讲解各种语法细节,还要对这些地方加以认证,以帮助大家能够感知到这些细节的存在更好的理解"类和对象"的玩法!
埋头编程
2024/11/15
1750
【C++】踏上C++的学习之旅(六):深入“类和对象“世界,掌握编程的黄金法则(一)
初识C++ · 类和对象(上)
C语言是一门面向过程的语言,注重的是解决问题的过程,举个例子——洗衣服,洗衣服的过程是:拿衣服——放进洗衣机——放洗衣液——放水——打开洗衣机——开始工作——结束——晾衣服,注重整个过程,C++是一门面向对象的语言,注重的是解决问题时候涉及的对象,比如洗衣服的时候涉及到了衣服,洗衣机,水,洗衣液等对象,注重的是对象交互来解决某个问题。
_lazy
2024/10/16
890
初识C++ · 类和对象(上)
python开发第六篇--递归函数和面
面向过程的程序设计的核心是过程(流水线式思维),过程即解决问题的步骤,面向过程的设计就好比精心设计好一条流水线,考虑周全什么时候处理什么东西。
py3study
2020/01/03
3380
从基础入门到学穿C++(类和对象篇)【超详细】【一站式速通】
C语言是一种面向过程的语言,C++和python、java一样都是一种面向对象的语言。
see.
2024/06/04
1361
从基础入门到学穿C++(类和对象篇)【超详细】【一站式速通】
【c++】类和对象(一)
在面向过程编程中,我们关注的是如何一步一步地执行这些任务,每个步骤都是一个过程或函数,我们按照顺序调用它们,最终得到想要的结果。这里的食材和步骤是分开的,首先我们定义了食材(数据),然后通过一系列的函数(步骤)来处理这些食材
用户11029103
2024/04/02
1220
【c++】类和对象(一)
Python面向对象编程(一)
1.面向过程的程序设计:核心是过程二字,过程指的是解决问题的步骤,即先干什么再干什么......面向过程的编程就好比设计一条流水线,是一种机械式的思维方式。
py3study
2020/01/07
3330
Python面向对象编程(一)
【C++】42道面试经典问题总结
C和C++的内存分布没有区别,usr space (reserve、.text、.rodata、.bss、heap stack 命令行参数和环境变量)+kernal space(ZONE_DMA 、ZONE_NORAMAL、ZONE_HIGHMEM)
洁洁
2024/09/11
2210
Java教程分享Java面向对象与面向过程[通俗易懂]
Java教程分享Java面向对象与面向过程,面向对象: 是一种看待问题, 解决问题的思维方式, 着眼点在于找到一个能够帮助解决问题的实体, 然后委托这个实体来解决问题
全栈程序员站长
2022/09/15
2270
【C++初阶】类和对象修炼上
C语言是面向过程的语言,关注的是过程,把洗衣服这件事拆分成浸泡,漂洗,脱水,晾干等过程,把过程写成函数,最后调用函数来完成;
MicroFrank
2023/01/16
7790
第二阶段-Java面向对象:【第一章 面向对象】
在我们正式进入学习这部分前,了解一下面向过程和面向对象这两个概念,对于我们 接下来的学习有很大的好处。别急,下面我就来和你说一说。
BWH_Steven
2019/08/09
6080
什么是面向对象? Java 的灵魂概念
为满足移动端和PC端的双重阅读体验,以及文章质量的保证,开始重构的以及新写的文章都会基于 “语雀” 平台编写,公众号会同步刚发布的文章,但随后的修改或者更新只会在语雀中维护。
BWH_Steven
2021/09/22
5520
什么是面向对象? Java 的灵魂概念
【 JavaSE 】 类和对象
作用:this表示当前对象引用(注意不是当前对象),可以借助 this 来访问对象的字段和方法
用户9645905
2022/11/30
4940
【 JavaSE 】 类和对象
【C++篇】类与对象(上篇):从面向过程到面向对象的跨越
大家好,我是“我想吃余”,很高兴你能和我一起进入到C++的学习中,我会将我的学习过程中的宝贵经验不遗余力的输入到文章中,希望可以帮助到你的学习。本文涵盖了从面向过程与面向对象的区别,到类的定义、访问限定符、封装、作用域、实例化、对象大小计算,以及this指针等内容。
我想吃余
2025/03/31
1620
【C++篇】类与对象(上篇):从面向过程到面向对象的跨越
Java基础语法(七)——类和对象
  相信大家都吃过月饼,我们做月饼的模子就是一个类,而通过这个模子可以做出月饼,那么在这个例子当中,类就是那个模子,而月饼就是那个对象,所以月饼就是一个实体。一个模子可以实例化无数个对象。
RAIN7
2021/08/11
5590
开源图书《Python完全自学教程》8.1面向对象
有的资料将这一章内容命名为“面向对象”,虽然没有错误,但这并不很 Pythonic ,因为 Python 中的函数是第一类对象,在前一章中已经开始“面向对象”了。其实不仅仅是第7章,本书从一开始,就在“面向对象”。那么,本章的类与对象有什么关系?为什么很多自学者会在学到本章的时候遇到困难?如何跨过这个难关?请读者满怀信心地认真学习本章和第9章,严格地执行各项学习建议。“漫卷诗书喜欲狂”的成功愉悦就在不远的将来。
老齐
2022/07/06
3720
开源图书《Python完全自学教程》8.1面向对象
相关推荐
C嘎嘎入门篇:类和对象(1)
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档
本文部分代码块支持一键运行,欢迎体验
本文部分代码块支持一键运行,欢迎体验