P4136 谁能赢呢？题解

· · 题解

题目大意

给定一个 n\times n 的棋盘，每次只能向上下左右四个方向移动一格，且移动过的格子不能再次移动。两人以最优策略玩这个游戏，问最后的赢家。

题目分析

如果二人均用最优策略走，那么双方都会避免自己被堵在走过的格子里面出不去的情况。举个例子，如果 (2,2),(3,3) 处的格子已经被走过，现在棋子在 (3,4) 处，玩家为让对方被困在 (2,3) 的格子里而周围一圈都被走过，肯定会选择走在 (2,4) 处，这样接下来另一位玩家肯定会走 (2,3) 处，这样就不会困死在这里。第一位玩家就会走 (1,3) 处，以此类推，他们最终会走遍棋盘上所有的格子。

容易发现，共有 n^2 个格子的棋盘移动数量为 n^2-1 次。当 n 为偶数时，n^2-1 为奇数，最后后手会无法移动，先手胜；反之后手胜利。