Retreats的专栏

题目链接:?pid=2147

题目大意:就是有一个游戏,在一个n*m的矩阵中起始位置是(1,m),走到终止位置(n,1);游戏规则是只能向左,向下,,左下方向走,想走到终点的为获胜者。

这一题就是巴什博弈,自学的孩子苦啊,网上找的资料还是有些不懂,先存着:

只要把PN状态图描绘出来就行了:

/*

* 博弈论:组合博弈* 必败点(P点) :前一个选手(Previous player)将取胜的位置称为必败点。* 必胜点(N点) :下一个选手(Next player)将取胜的位置称为必胜点。

* 必败(必胜)点的属性:* (1) 所有终结点是必败点(P点);* (2) 从任何必胜点(N点)操作,至少有一种方法可以进入必败点(P点);* (3)无论如何操作, 从必败点(P点)都只能进入必胜点(N点).* 由上面的属性得到该题的算法:* 步骤1:将所有终结位置标记为必败点(P点);* 步骤2: 将所有一步操作能进入必败点(P点)的位置标记为必胜点(N点)* 步骤3:如果从某个点开始的所有一步操作都只能进入必胜点(N点) ,则将该点标记为必败点(P点) ;* 步骤4: 如果在步骤3未能找到新的必败(P点),则算法终止;否则,返回到步骤2。* 由上面的算法计算一个例子:* 我们可以把问题转换成从(1,1)走到(n,m) (方便等下得出结论)

* 但n=8,m=9的情况NNNNNNNNNPNPNPNPNPNNNNNNNNNPNPNPNPNPNNNNNNNNNPNPNPNPNPNNNNNNNNNPNPNPNPNP*初始点(1,1)为N所以输出Wonderful!*从这里例子就可以很清楚得看出当n和m都为奇数时,初始点(1,1)才会是P。*因此该题只需判断n,m是否同时为奇数即可。*/

#include<iostream>using namespace std;int main(){int n,m;while(cin>>n>>m,m+n){puts((n%2&&m%2)?"What a pity!":"Wonderful!");}return 0;}

读书破万卷,下笔如有神。

Retreats的专栏

相关文章:

你感兴趣的文章:

标签云: