草庐IT

「博弈dp」棋盘游戏

孤星·璀璨 2023-03-28 原文

本题为12月30日22寒假集训每日一题题解

题目来源:(未知)

题面

题目描述

懒羊羊和小灰灰在玩一种棋盘游戏,棋盘的尺寸为n个方格*m个方格。一开始在棋盘的右上角(1,m)放一枚硬币,每次一个人可以将硬币向左、下或左下的方格移动。

当某个人无法再移动硬币了,那么这个人就输了。游戏总是懒羊羊先开始,如果他们两个每步都是最优策略,则谁将赢得游戏?

输入

输入包含多组测试数据。每组输入两个整数n和m(0< n, m <=2000)。
当n = m = 0时,输入结束。

输出

对于每组输入,如果懒羊羊赢,输出“Wonderful!”,否则输出“What a pity!”。

样例输入 Copy

5 3
5 4
6 6
0 0

样例输出 Copy

What a pity!
Wonderful!
Wonderful!

思路分析

显然此题直接按照博弈论的基础做法——动态规划即可完成.

在博弈论问题中,状态即为当前规模问题的胜负情况(每次每方操作,都会缩小问题的规模,同时交换先后手),状态转移方程即为游戏的规则,不过由于先后手交换需要取反.由于先手无法移动的状态只可能是左下角的那个格子,所以我们可以将其定义为初始状态,然后从这个状态开始,反推回右上角的格子即可.右上角格子的状态即为当前游戏的结果是胜是负.这里注意是多组输入,每组输入dp数组需要重新初始化.

参考代码

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3, "Ofast", "inline")

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

bool dp[2010][2010] = {0}; // 状态转移用数组,记录每个状态先手的胜负情况

int main()
{
    ios::sync_with_stdio(false);

    int n, m;

    while (cin >> n >> m && n != 0)
    {
        memset(dp, 0, sizeof(dp)); // 重置dp数组

        // 从左下角的格子开始状态转移
        for (int i = n - 1; i >= 0; i--)
        {
            for (int j = 0; j < m; j++)
            {
                // 当前状态能由其左、下、左下三个状态转移得到,只要一个状态为真,当前状态即为真.注意每次转移由于先后手转换,需要取反,同时要验证是否越界
                if (i < n - 1)
                {
                    dp[i][j] |= !dp[i + 1][j];
                }
                if (j > 0)
                {
                    dp[i][j] |= !dp[i][j - 1];
                }
                if (i < n - 1 && j > 0)
                {
                    dp[i][j] |= !dp[i + 1][j - 1];
                }
            }
        }

        if (dp[0][m - 1]) // 右上角的初始状态即代表当前游戏是胜是负
        {
            cout << "Wonderful!\n";
        }
        else
        {
            cout << "What a pity!\n";
        }
    }

    return 0;
}

"正是我们每天反复做的事情,最终造就了我们,优秀不是一种行为,而是一种习惯" ---亚里士多德

有关「博弈dp」棋盘游戏的更多相关文章

  1. ruby - 我需要从 facebook 游戏中抓取数据——使用 ruby - 2

    修改(澄清问题)我已经花了几天时间试图弄清楚如何从Facebook游戏中抓取特定信息;但是,我遇到了一堵又一堵砖墙。据我所知,主要问题如下。我可以使用Chrome的检查元素工具手动查找我需要的html-它似乎位于iframe中。但是,当我尝试抓取该iframe时,它​​是空的(属性除外):如果我使用浏览器的“查看页面源代码”工具,这与我看到的输出相同。我不明白为什么我看不到iframe中的数据。答案不是它是由AJAX之后添加的。(我知道这既是因为“查看页面源代码”可以读取Ajax添加的数据,也是因为我有b/c我一直等到我可以看到数据页面之后才抓取它,但它仍然不存在)。发生这种情况是因为

  2. python - Ruby 或 Python 的 3d 游戏引擎? - 2

    关闭。这个问题不符合StackOverflowguidelines.它目前不接受答案。要求我们推荐或查找工具、库或最喜欢的场外资源的问题对于StackOverflow来说是偏离主题的,因为它们往往会吸引自以为是的答案和垃圾邮件。相反,describetheproblem以及迄今为止为解决该问题所做的工作。关闭9年前。Improvethisquestion是否有适用于这些的3d游戏引擎?

  3. ruby - 使用 Ruby 编写 Unity 游戏 - 2

    所以我看到unity支持c#、JS和Boo。我可以学习其中一个,但我想制作一个“编译器”或类似的东西,让我可以编写ruby​​代码并输出JS代码或制作一个可以被Unity编译器读取的层。这有可能吗?我愿意在这方面投入很多时间并且有相当多的经验。 最佳答案 如果您的问题实际上是“我如何将Ruby编译为JavaScript”,那么这更容易回答:Opal:RubytoJavaScriptcompiler但是,学习其中一种受支持的语言会更好。当运行的是用另一种语言解释的代码时,很难调试“您的”代码。

  4. 【Unity游戏破解】外挂原理分析 - 2

    文章目录认识unity打包目录结构游戏逆向流程Unity游戏攻击面可被攻击原因mono的打包建议方案锁血飞天无限金币攻击力翻倍以上统称内存挂透视自瞄压枪瞬移内购破解Unity游戏防御开发时注意数据安全接入第三方反作弊系统外挂检测思路狠人自爆实战查看目录结构用il2cppdumper例子2-森林whoishe后记认识unity打包目录结构dll一般很大,因为里面是所有的游戏功能编译成的二进制码游戏逆向流程开发人员代码被编译打包到GameAssembly.dll中使用il2ppDumper工具,并借助游戏名_Data\il2cpp_data\Metadata\global-metadata.dat

  5. Unity游戏开发:背包系统的实现 - 2

    背包是游戏中经常使用的一个组件,它负责管理玩家在游戏中所获得的道具。一个完整的背包系统应当具有将物品放置进背包、对背包内物品进行管理和使用背包内物品等功能。而往往一个背包系统的逻辑关系较为复杂,如果把所有功能都放在一个脚本中实现会使代码显得十分冗杂且缺乏逻辑。所以在背包系统的设计过程中,我们常将其分解为数据、逻辑和UI三部分分别来进行完成。一、UI设计以CottonPuzzle中的背包设计为例,我们需要有物品展示栏、物品切换按键和物品提示信息等部分。在Canvas中创建ItemHolder,在ItemHolder中创建LeftButton和RightButton控制物品的左右切换、Slot来控

  6. 仍在积极维护的 Ruby 游戏框架? - 2

    关闭。这个问题不符合StackOverflowguidelines.它目前不接受答案。我们不允许提问寻求书籍、工具、软件库等的推荐。您可以编辑问题,以便用事实和引用来回答。关闭7年前。Improvethisquestion我发现很难调查使用Ruby进行游戏编程的选项。其他帖子和文章中提到的几个包装器和框架不再维护或使用。Gosu/Ruby似乎仍然活跃:官方论坛上的讨论一直很稳定。是否还有其他积极维护的ruby​​游戏框架?编辑:我发现使用MacRuby进行大量游戏开发。

  7. ruby - 基于 OOP 的文本游戏中的优雅命令解析 - 2

    我正在玩用Ruby编写MUD/文本冒险(请不要笑)。谁能给我任何关于解析输入文本的优雅的、基于oop的解决方案的建议?我们在这里谈论的只是“把魔杖放在table上”更复杂的事情。但是一切都需要柔软;我想稍后轻松地扩展命令集。我目前的想法,稍微简化一下:每个项目类别(盒子、table、房间、播放器)都知道如何识别“属于”它的命令。游戏类理解一种特定于领域的语言,涉及诸如“将对象X移入对象Y”、“显示对象X的描述”等Action。游戏类询问房间中的每个项目是否识别输入命令。先说是赢。然后它将控制传递给项目类中处理命令的方法。此方法重新表述DSL中的命令,将其传递回游戏对象以实现它。必须有一

  8. ruby - 此修改后的二十一点游戏的最佳获胜策略是什么? - 2

    问题有没有可以保持的最佳值(value),这样我才能赢得尽可能多的比赛?如果是这样,那是什么?编辑:是否可以为给定的限制计算出确切的获胜概率,而与对手的所作所为无关?(自大学以来,我还没有做过概率和统计)。我有兴趣将其作为与模拟结果进行对比的答案。编辑:修复了我算法中的错误,更新了结果表。背景我一直在玩改进的二十一点游戏,其中对标准规则进行了一些相当烦人的规则调整。我已将与标准二十一点规则不同的规则斜体化,并为不熟悉的人添加了二十一点规则。修改二十一点规则正是两个人类玩家(经销商无关)每个玩家面朝下发两张牌双方玩家_ever_都不知道对手纸牌的_any_的值在_both_完成手牌之前,

  9. ruby-on-rails - 选择 Ruby on Rails 作为基于浏览器的在线游戏平台 - 2

    对于类似Travian的在线策略游戏,我有一些(我认为)非常棒的想法。有些内容我还没有想通,还有一些我还不知道的挑战。这是一个相当大的项目,对于(还)不是熟练的Web开发人员的人来说可能太重了。我还是想试一试,但我在选择平台时遇到了麻烦。世界上的“规模”最近被抛得一团糟,我看到RubyonRails因规模不佳而受到抨击,所以我来这里是为了得到一些答案。我喜欢RubyonRails,无论是Ruby还是Rails。我当然不是这方面的专家,但我喜欢使用它。我之前也使用过Python+Django,也使用过PHP(我不喜欢它。)理想情况下,假设每个服务器有7000名玩家,大概每秒要处理大量数据

  10. U3D游戏开发工程师正确入行姿势指南 - 2

    2021年,游戏圈上演了一场精彩绝伦的抢人大战。在上海游戏圈,年薪百万的人越来越多了。据多名HR估算,在上海,过去一年TA、引擎、美术等稀缺岗位拟的薪资涨幅大概在20%-30%左右。某位圈内知名资深游戏猎头对此发出感叹:“50K的数值策划、角色原画;70K的技术美术;80K的技术总监...他们的年薪总包都接近百万,就连应届生入行的薪资也水涨船高,这要是放在以往都是不敢想象的”。以往含年薪、期权等的年总包收入上百万元,起码得是总监级别。如今工作五六年的人从广深跳到上海游戏公司,年薪能从50-70万跃上100万元,拿百万年薪的游戏从业者越来越多了上海游戏圈近年发展迅速,既有颇具发展潜力的中生代F4

随机推荐