HDU-5754 Life Winner Bo (博弈论)

2021-02-18 02:18

阅读：768

n*m的棋盘，一枚棋子要从左上角（0，0）到右下角，两个人轮流移动，谁移动到最后一步谁胜利，移动规则如下，有四种棋子：

1、king 国王向右，向下，或者向右下移动一格

2、castle 车向右，或者向下移动任意格

3、knight 马向2*3的矩阵的另一个角移动

4、queen 王后移动到同一行、列、斜线的任意位置

思路：

很明显这个是一个博弈的题目。他好在有四种棋子，分别对应四种走法，也就是将四个博弈结合在了一起。

将棋盘看作两堆石子，棋子移动取就是两堆石子，谁先取完谁胜利，一堆石子n-1个，一堆m-1个。

将四种博弈分别分析

1、king 国王向右，向下，或者向右下移动一格，简化成石子问题就是可以在其中一堆取一个（向右、向下）或者在两堆中各取一个（向右下）。最终取到(0,0) 那就很明显了，最终结果是偶偶的，每一次偶偶都只能变成奇偶，偶奇，奇奇，然而这三种都能一次变成偶偶。于是就有答案了，谁面对偶偶的局势谁就输，对方只要保持每次都让他面对偶偶的局势就能保证取走最后的石子。这是对于n-1和m-1，对于n,m就是当n,m都为奇数时第一个人面对必败态，否则第一个人胜利。

2、castle 车向右，或者向下移动任意格，简化成石子问题就是从某一堆中取出任意个，简单的nim博弈就能解决。同样也可以理解为一开始就保证和终点在一条对角线上，一定是先手赢，所以必胜策略就是先手移动到对角线上——然而如果一开始就是一个正方形，那先手肯定必败了。

3、knight 马向2*3的矩阵的另一个角移动， Knight的移动方法跟马一样走日字，它比较难处理，因为它有和局的情况（比如某个人一直往右走，导致对面无路可走）使对手无法获得胜利…这样的情况看似麻烦，其实我们也可以用相同的思想分析必胜和必败状态。我们先区分能分出胜负的局面和平局的局面，通过画图，我们可以发现（2，3）和（3，2）这样的情况是一定先手必胜的，而想（3，3）这种情况就无法达到，更进一步，我们发现（4，4）这种情况是一定必败的，而其他比它小的情况全部是平局。更进一步，我们发现（5，6）这种情况也是必胜的：我们只需要先手走到（2，3）这个点就可以，在之前，我们知道（4，4）是先手必败，而在这里，我们如果把（2，3）看作起始点，把（5，6）看作终点，其组成的正方形和刚才那种情况一模一样：这说明这就是一种可以区分胜负的局面，从（4，4）开始，（7，7），（10，10）….均为先手必败，然而我们如果可以先手走到这样一种必败的局面，我们即是必胜的——而其余情况，全为和局。到这里我们就可以写出最终结果了：当终点减去起点的坐标能被3整除的时候，先手必败；对于必胜条件，我们只需要判断（2，3）和（3，2）是否可以达到必败局面就可以了。

4、queen 王后移动到同一行、列、斜线的任意位置，简化成石子问题就是可以在一堆中去任意个，也可以在两堆中取相同个。经典的威佐夫博弈问题，我们可以直接求解。

代码：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include string>
#include 
#include 
#include 
#include set>

#define IO ios::sync_with_stdio(false);\
    cin.tie(0);    cout.tie(0);

typedef long long LL;
const long long INF = 0x3f3f3f3f;
const long long mod = 1e9+7;
const double PI = acos(-1.0);
const int maxn = 100000;
const char week[7][10]= {"Monday","Tuesday","Wednesday","Thursday","Friday","Saturday","Sunday"};
const char month[12][10]= {"Janurary","February","March","April","May","June","July",
                           "August","September","October","November","December"
                          };
const int daym[2][13] = {{0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31},
    {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}
};
const int dir4[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
const int dir8[8][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}, {1, 1}, {-1, -1}, {1, -1}, {-1, 1}};

using namespace std;

int main()
{
    IO;
    int T;
    cin>>T;
    int logo=1;
    while(T--)
    {
        int t,n,m;
        cin>>t>>n>>m;
        n--;
        m--;
        if(t==1)
        {
            if(n%2==0&&m%2==0)
                cout"G"endl;
            else
                cout"B"endl;
        }
        if(t==2)
        {
            if(n==m)
                cout"G"endl;
            else
                cout"B"endl;
        }
        if(t==3)
        {
            if (n==m&&n%3==0)
                cout"G"endl;
            else if (n-1==m&&(n-1)%3==1)
                cout"B"endl;
            else if (n==m-1&&n%3==1)
                cout"B"endl;
            else
                cout"D"endl;
        }
        if(t==4)
        {
            int ak=0;
            int a=n;
            int b=m;
            double k;
            k=(sqrt(5.0)+1.0)/2.0;
            if(a>b)
            {
                t=a;
                a=b;
                b=t;
            }
            t=b-a;
            ak=(int)(t*k);
            if(a==ak)
                cout"G"endl;
            else
                cout"B"endl;
        }
    }
    return 0;
}

上一篇：C#堆和栈的入门理解

下一篇：Windows下GO开发环境配置

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：HDU-5754 Life Winner Bo (博弈论)
文章链接：http://soscw.com/essay/56844.html

亲，登录后才可以留言！

HDU-5754 Life Winner Bo (博弈论)

思路：

代码：

评论

热门文章

推荐文章

最新文章

置顶文章