算法学习之路|棋盘问题(博弈)-阿里云开发者社区

开发者社区> 人工智能> 正文

算法学习之路|棋盘问题(博弈)

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

小明和小红在玩一种棋盘游戏,棋盘的尺寸为n个方格*m个方格。一开始在棋盘的右上角(1,m)放一枚硬币,每次一个人可以将硬币向左、下或左下的方格移动。
当某个人无法再移动硬币了,那么这个人就输了。游戏总是小明先开始,如果他们两个每步都是最优策略,则谁将赢得游戏?

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

输出格式
对于每组输入,如果小明赢,输出“Wonderful!”,否则输出“What a pity!”。
样例输入
5 3
5 4
6 6
0 0
样例输出
What a pity!
Wonderful!
Wonderful!

解题思路
简单博弈论题,谁走最后一步到达角落,谁就获胜(后一个人无路可走)。
来考虑最后的情况,如果棋子距离左边下边都只剩两格,那么下一个动的人一定输。
讨论两种情况:

  1. 向左或向下走,后一个走的人一定也走向左或向下的路线,这样能使棋子到达一个边界且距另一条边界2格,那么之后的两步必然两个人都各走一步。后走的人抢先到达角落到达角落,先走的那个人就无法移动了(输)。(例:(2,2)-(2,1)-(2,0)-(1,0)-(0,0)(输))
  2. 向左下走,那么后走的人也一定向左下走,这样就抢先到达(0,0),获胜,先走的人输。
    再考虑一般情况:棋子距两边界格数均为偶数。

可以把上面情况一般化,后走的人一定跟随先走的人的方向移动,使得两人各移动一步后棋子距两边界格数保持偶数(包含0),同理,先走必输。
由此,即可得出结论。

#include<stdio.h>
int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF&&n&&m)
    {
        int a=n-1,b=m-1;
        if(a%2==0&&b%2==0)
            printf("What a pity!\n");
        else printf("Wonderful!\n");
    }
    return 0;
}

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

其他文章