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

简介: 小明和小红在玩一种棋盘游戏,棋盘的尺寸为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;
}
目录
相关文章
|
2月前
|
机器学习/深度学习 数据采集 搜索推荐
Paper Digest | 突破个性化推荐数据稀疏性:长尾增强的图对比学习算法研究
本文提出了一种新的长尾增强的图对比学习方法(LAGCL),该方法促使模型同时兼顾头部节点与尾部节点之间的知识,并通过长尾增强技术来使模型产出更均匀更准确的节点表征,从而改进基于 GNN 的推荐任务。
|
2月前
|
算法 网络协议 Linux
【Cisco Packet Tracer】交换机的自学习算法
【Cisco Packet Tracer】交换机的自学习算法
53 0
|
3月前
|
算法 安全 数据安全/隐私保护
C/C++学习 -- RSA算法
C/C++学习 -- RSA算法
34 0
|
3月前
|
机器学习/深度学习 算法
机器学习 - [集成学习]Bagging算法的编程实现
机器学习 - [集成学习]Bagging算法的编程实现
32 1
|
8天前
|
机器学习/深度学习 算法 前端开发
Scikit-learn进阶:探索集成学习算法
【4月更文挑战第17天】本文介绍了Scikit-learn中的集成学习算法,包括Bagging(如RandomForest)、Boosting(AdaBoost、GradientBoosting)和Stacking。通过结合多个学习器,集成学习能提高模型性能,减少偏差和方差。文中展示了如何使用Scikit-learn实现这些算法,并提供示例代码,帮助读者理解和应用集成学习提升模型预测准确性。
|
8天前
|
机器学习/深度学习 算法 Python
使用Python实现集成学习算法:Bagging与Boosting
使用Python实现集成学习算法:Bagging与Boosting
18 0
|
15天前
|
算法
【算法学习--字符串】(不含KMP算法)
【算法学习--字符串】(不含KMP算法)
|
1月前
|
Rust Dart 算法
55.3k star!开源算法教程,附带动画图解,学习算法不再苦恼!
55.3k star!开源算法教程,附带动画图解,学习算法不再苦恼!
|
1月前
|
算法 C++ 计算机视觉
Opencv(C++)学习系列---Laplacian拉普拉斯边缘检测算法
Opencv(C++)学习系列---Laplacian拉普拉斯边缘检测算法
|
1月前
|
算法 C++ 计算机视觉
Opencv(C++)学习系列---Canny边缘检测算法
Opencv(C++)学习系列---Canny边缘检测算法