51Nod - 1534 - 棋子游戏（博弈论）

本文主要是介绍51Nod - 1534 - 棋子游戏（博弈论），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：http://www.51nod.com/Challenge/Problem.html#!#problemId=1534&judgeId=1534

波雷卡普和瓦西里喜欢简单的逻辑游戏。今天他们玩了一个游戏，这个游戏在一个很大的棋盘上进行，他们每个人有一个棋子。他们轮流移动自己的棋子，波雷卡普先开始。每一步移动中，波雷卡普可以将他的棋子从(x,y) 移动到 (x-1,y) 或者 (x,y-1)。而瓦西里可以将他的棋子从(x,y) 移动到 (x-1,y),(x-1,y-1) 或者 (x,y-1)。当然他们可以选择不移动。

还有一些其它的限制，他们不能把棋子移动到x或y为负的座标，或者移动到已经被对手占据的座标。最先到达（0，0）的人获胜。

现在给定他们棋子的座标，判断一下谁会获胜。

 

Input

单组测试数据。
第一行包含四个整数xp,yp,xv,yv (0≤xp,yp,xv,yv≤10^5) ，表示波雷卡普和瓦西里棋子的座标。
输入保证他们的棋子在不同位置，而且没有棋子在（0，0）。

Output

如果波雷卡普获胜，输出Polycarp，否则输出Vasiliy。

Input示例

样例输入1
2 1 2 2

Output示例

样例输出1
Polycarp

思路：当可以拦截瓦西里，或者步数比瓦西里少时都是Polycarp获胜，当（xp==xv&&yp<yv） （xp<xv&&yp==yv）和 (xp<xv&&yp<yv)都可以拦截，波雷卡普的最少步数是x+y，因为瓦雷西可以斜着走所以最少步数是max（x，y）。注意当步数相等时是Polycarp获胜，因为波雷卡普先走。

ACDAIMA：

#include<stdio.h>
#include<iostream>
#include<math.h>
using namespace std;
int main()
{int xp,yp,xv,yv;while(cin>>xp>>yp>>xv>>yv){if((xp<xv&&yp==yv)||(xp==xv&&yp<yv)||(xp<xv&&yp<yv)||((xp+yp)<=max(xv,yv)))cout << "Polycarp" << endl;elsecout << "Vasiliy" << endl;}return 0;
}

 

 

 

这篇关于51Nod - 1534 - 棋子游戏（博弈论）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---