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

简介: 小明和小红在玩一种棋盘游戏,棋盘的尺寸为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月前
|
存储 算法
数据结构与算法学习二二:图的学习、图的概念、图的深度和广度优先遍历
这篇文章详细介绍了图的概念、表示方式以及深度优先遍历和广度优先遍历的算法实现。
68 1
数据结构与算法学习二二:图的学习、图的概念、图的深度和广度优先遍历
|
1月前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
数据结构与算法系列学习之串的定义和基本操作、串的储存结构、基本操作的实现、朴素模式匹配算法、KMP算法等代码举例及图解说明;【含常见的报错问题及其对应的解决方法】你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
|
2月前
|
缓存 算法 Java
JVM知识体系学习六:JVM垃圾是什么、GC常用垃圾清除算法、堆内存逻辑分区、栈上分配、对象何时进入老年代、有关老年代新生代的两个问题、常见的垃圾回收器、CMS
这篇文章详细介绍了Java虚拟机(JVM)中的垃圾回收机制,包括垃圾的定义、垃圾回收算法、堆内存的逻辑分区、对象的内存分配和回收过程,以及不同垃圾回收器的工作原理和参数设置。
85 4
JVM知识体系学习六:JVM垃圾是什么、GC常用垃圾清除算法、堆内存逻辑分区、栈上分配、对象何时进入老年代、有关老年代新生代的两个问题、常见的垃圾回收器、CMS
|
2月前
|
算法
动态规划算法学习三:0-1背包问题
这篇文章是关于0-1背包问题的动态规划算法详解,包括问题描述、解决步骤、最优子结构性质、状态表示和递推方程、算法设计与分析、计算最优值、算法实现以及对算法缺点的思考。
99 2
动态规划算法学习三:0-1背包问题
|
1月前
|
机器学习/深度学习 人工智能 自然语言处理
【EMNLP2024】基于多轮课程学习的大语言模型蒸馏算法 TAPIR
阿里云人工智能平台 PAI 与复旦大学王鹏教授团队合作,在自然语言处理顶级会议 EMNLP 2024 上发表论文《Distilling Instruction-following Abilities of Large Language Models with Task-aware Curriculum Planning》。
|
1月前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习(8)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
1月前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习之顺序表【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
顺序表的定义和基本操作之插入;删除;按值查找;按位查找等具体详解步骤以及举例说明
|
1月前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之单双链表精题详解(9)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
1月前
|
存储 Web App开发 算法
2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构之单双链表按位、值查找;[前后]插入;删除指定节点;求表长、静态链表等代码及具体思路详解步骤;举例说明、注意点及常见报错问题所对应的解决方法
|
1月前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!