Felix021

WHUACM 20080608 Day4个人赛B题

描述：在一个N*M的矩阵中有两个人AB分别处于行列都不相同的两个位置。AB轮流走动，可以在棋盘范围内上下左右走任意步数。若某个人停在或走过对方当前所在的行或列，则对方赢。给出矩阵的大小和AB的初始位置，A先走，如果AB都尽可能走好，问谁会赢。

分析：
不失一般性的设AB所在的位置分别为(Ax,Ay) (Bx,By)， Ax<Bx, Ay<By(因为如果小于号不成立的话把矩阵相应翻转一下就行了)
设x=bx-ax  y=by-ay, 可以证明，把AB分别平移到(0, 0) (x, y) 是和原先的位置等价的：如果A向上移动x1步，B向上移动x1步；A向左移动y1，B也向左移动y1步，这样B就可以把A逼到左上角的(0,0) 同时自己就落在了(x,y)；如果A不往上/左走，那么B就可以把A和自己的距离控制在一个更小的范围内，如果A不能保证赢的话，这只会让A输得更快，这在下面可以看出来。
接下来我们就讨论当A在(0,0) B在(x,y)的时候A先走，谁会是赢家。
首先可以从最简单的开始推导。
1.如果x=y=1，那么显然B要赢。
2.如果x>1 y=1，那么A显然要赢：A走到(x-1,0)，根据前面所说，A就可以把B逼到右下角的位置，于是A赢。换成x=1 y>1结果也是A赢。
3.如果x=y=2，那么如果A向下走一步，B向左走一步；或者A向右走一步，B向上走一步。于是A就只能往回走，B跟上，就回到了情况1。
……
多推导几个就会发现，其实所有情况可以归类为 a. x=y 和 b. x!=y 两种情况
a. x=y，如果A向下n步，B向左n步；或者A向右n步，B向上n步。于是B可以把A逼到(0,0), 自己在(x-n, y-n)，反复下去就回到情况1，B赢。
b. x!=y, 假设x>y，那么A可以走到(x-y, 0) B在(x, y)，这时B要先走，这就等同于AB互换名字的情况a，A赢。

于是解法就出来了：

---

欢迎扫码关注：

转载请注明出自 ，如是转载文则注明原出处，谢谢:)
RSS订阅地址: https://www.felix021.com/blog/feed.php 。