欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

HDU-2147 kiki's game 巴什博弈

程序员文章站 2022-06-29 08:45:56
...

HDU-2147 传送门


最近小明很闲,找了小华下棋。 棋盘的大小是n*m,小明突然想到一个新的玩法,首先有个卒放在棋盘的右上角(1,m)的位置。 每一次小明或者小华可以将这个卒向左移一步或者向下移一步,或者向左下移一步 谁不能移动谁就输了。小明先移动棋子卒,小明会赢吗?假设玩家都是最优决策。
Input
多组输入,每行包括两个数字n,m (0 < n , m < = 2000 )当n=0,m=0时输入结束.
Output
如果小明获胜则重拳出击print"Wonderful!",否则bb一句print"What a pity!"

Sample Input
5 3
5 4
6 6
0 0

Sample Output
What a pity!
Wonderful!
Wonderful!

虽然我写了四十分钟,但 不得不承认,这是个简单的博弈题。


我们先来看一下题目意思,首先给出一个n*m的棋盘,棋子起点位置为右上角,每次只能向左向下,或向左下三个方向中的一个方向移动一步,问小明先走,他是否可以获胜。

首先我们读题之后可以明确一点,棋盘中的每一个位置都只有两种状态,也就是必胜态和必败态,现在我们不知道别的位置的情况,但是有一个位置可以确定,那就是左下角那个位置必败。比如是一个1*1的地图,那显然小明输。


下面给出一张图用来演示推演过程

(用红点表示必败点,蓝点表示必胜点)

HDU-2147 kiki's game 巴什博弈

知道左下角必败之后如何继续推演呢?上面已经说过,棋盘中的每一个位置都只有两种状态,也就是必胜态和必败态那么只要能将棋子移动到必败点的位置,就是必胜点。当前已知的必败点就是左下角,又有,棋子只能向三个方向移动,所以可以得到下图:

HDU-2147 kiki's game 巴什博弈

又有任意一点的状态,只与左、下、左下三个位置的状态有关,所以我们只要知道这三个点的状态,就可以推得该点的状态。

另外,左边这条线和下面这条线上的所有点,没有任何别的选择,只能向下、向左移动,进而可以得到下图:

HDU-2147 kiki's game 巴什博弈

接下来是巴什博奕中最重要的两点:

  • 任何可以转化为必败态的状态都是必胜态。
  • 任何只能转化为必胜态的状态都是必败态。

下面给出四个黄点的位置用这句话来分析一下

(黄点从左到右,从上到下标号)

HDU-2147 kiki's game 巴什博弈

  • 第一个黄点可以向左移动一步,进入必败态,因此它是必胜态。
  • 第三个黄点可以向下移动一步,进入必败态,因此它也是必胜态。(第二个黄点此时还不确定他下面位置的状态,因此无法推演)
  • 满足推演条件后,第二个黄点只能进入必胜态,因此它是必败态。
  • 第四个黄点可以向左下移动一步,进入必败态,因此它是必胜态。

按这种方式推演下去,很容易得到下图:

由于我太懒,图没有画完全,但是 规律显而易见。

HDU-2147 kiki's game 巴什博弈

结论:只有横纵坐标都是奇数时,才是必败点,其余都为必胜点

代码如下:

#include <stdio.h>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <queue>
#include <deque>
#include <cstring>
#include <iterator>
#include <set>
#include <map>
using namespace std;
#define ll long long
int main()
{
    int n, m;
    while (cin >> n >> m)
    {
        if (!n && !m)
            break;
        if (n % 2 && m % 2)
            cout << "What a pity!" << endl;
        else
            cout << "Wonderful!" << endl;
    }
    return 0;
}
相关标签: 博弈