51nod 1534 棋子游戏(博弈)

1.0 秒 131,072.0 KB 20 分 3级题

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

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

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


P可以向上或向左或不动,V可以向上或向左或向左上或不动,算曼哈顿距离,V有改变奇偶性的机会,但是P可能可以去堵W的路(因为P可以不动一直堵着,那V就不能改变奇偶性了)

所以就是看P能不能堵到,要么比较x1+y1max(x2,y2),小的赢(相等的话还是P赢,因为先手先占位子),要么看看(x1,y1)是否在(x2,y2)左上方,能堵到就P赢,不然都是V赢

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<string>
#include<vector>
using namespace std;

int main(){
int x1,y1,x2,y2;
cin>>x1>>y1>>x2>>y2;
if(x1+y1<=max(x2,y2))puts("Polycarp");
else if(x1<=x2&&y1<=y2)puts("Polycarp");
else puts("Vasiliy");
return 0;
}
打赏
  • 版权声明: 本博客所有文章除特别声明外,著作权归作者所有。转载请注明出处!
  • Copyrights © 2018-2021 LeFlacon

奶茶一杯 快乐起飞

支付宝
微信