这类型题第一次接触 所以一开始想不出来 现在懂了 Math.abs(x2-x1)+Math.abs(y2-y1) %2
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); int x1 = sc.nextInt(); int y1 = sc.nextInt(); int x2 = sc.nextInt(); int y2 = sc.nextInt(); if((Math.abs(x2-x1)+Math.abs(y2-y1))%2 == 0) { System.out.println("Win"); } else System.out.println("Lose"); } }
来自网页EOJ大佬的解释:
要想清楚还是比较麻烦的,大力猜测结论与奇偶性相关,就稳了。
结论是:如果 |x1−x2|+|y1−y2| 是奇数,先手必胜,否则,后手必胜。
下面我们定义距离为两个玩家棋子间的曼哈顿距离,我们发现,每个玩家每个回合开始时距离的奇偶性是保持不变的,因为每个玩家移动时,距离的奇偶性都会发生改变,而到下个玩家移动时,奇偶性就会变回来。由于只有回合开始时距离为 1 时才是必胜态,所以回合开始时距离为偶数的玩家是一定赢不了的。
接着,证明不存在平局情况:
因为一方不可能输,所以想要赢,只要不断拉近距离即可。先来简单证明双方距离不会变大:
无论守方如何移动,双方的距离都最多增加 1,而攻方总能找到一个移动方向,使双方距离 −1。
因此,想要平局,守方只能保证距离不变。为了不拉近距离,守方肯定会选择远离一方的方向移动。双方之间的位置关系有两种可能:第一种,不在同一行也不在同一列;第二种,在同一行或同一列。
先来讨论第一种情况,我们假设守方在攻方的左上方,那守方只能向左或向上走,否则就会主动拉近距离。此时,攻方只要重复守方的移动即可。因为守方在攻方的左上方,因此如果守方一直向左或向上,肯定比攻方先碰到边界,最终被逼到边角,不得不向右或下方移动,不可能保证距离一直不变。
接着讨论第二种情况,我们假设守方在攻方的正上方,如果守方向左或向右,那攻方只要向上走,就会在不增加距离的情况下变成第一种情况,因此守方只能向上走,但这么走也早晚会碰到边界,最后不得不将情况变成第一种情况。
于是,我们知道两个棋子之间的距离只可能减小。因此,不存在平局情况,回合开始时距离为奇数的一方必胜。