Kiki’s game PN 图
title: 题目 [kiki's game](https://vjudge.csgrandeur.cn/problem/HDU-2147) 最近帅气的羊羊很闲，找到了美丽的驼驼下棋。 棋盘的大小是$n*m$,羊羊突然想到一个新的玩法，首先有个卒放在棋盘的右上角$(1,m)$的位置。 每一次羊羊或者驼驼可以将这个卒向左移一步或者向下移一步，或者向左下移一步 谁不能移动谁就输了。羊羊先移动棋子卒，羊羊会赢吗？假设玩家都是最优决策。 title: input 5 3 5 4 6 6 0 0 title: output What a pity! Wonderful! Wonderful! title: 思路
巴什博奕思路： 两堆 n,m 的石子, 可以每堆取一个或者同时取两堆中各一个。 由于是一个一个取,显然和奇偶性有关。 若只有一堆, 则奇数先手必胜。 若有两堆, 全为偶数时, 先手必败,因为后手总能把数量都维持成偶数。 一奇一偶时, 先手必胜,取一个奇数的就变成全偶数必输。 全奇时, 取两个变成全偶局面。
即含有奇数时先手必胜。 这里nm初始减一, 故为含有偶数时先手必胜。
PN图：
**必败点(P点)** :前一个选手(Previous player)将取胜的位置称为必败点。 **必胜点(N点)** :下一个选手(Next player)将取胜的位置称为必胜点。
实际上就是按照规则画图；有以下三条规则： 1. 每个图的末状态均为必败点P 2. 所有能够一步到达必败点的都是必胜点N 3. 所有能够一步到达必胜点的都是必败点 P 画图的时候，选定对角线定点里面的那个点位末状态，题上的说明，那么一般找的规则就是从最底边上，还有最开始的那一列开始确定P还是N点，这样很方便的看出，当行列都是奇数的时候，那么一定会必败点。
![[Pasted image 20220723214137.png]] 可以发现, 含有偶数的都是N点, 即必胜点。 title:代码 ~~~ c ++ #include <iostream> using namespace std; int main() {
int n, m; while (cin >> n >> m && (n || m)) { if (n % 2 == 0 || m % 2 == 0) cout << "Wonderful!\n"; else cout << "What a pity!\n" ; }
return 0; } ~~~