[itint5]跳马问题加强版 - 阿牧遥 - 博客园
首先由跳马问题一，就是普通的日字型跳法，那么在无限棋盘上，任何点都是可达的。证法是先推出可以由(0,0)到(0,1)，那么由对称型等可知任何点都可以到了。
有一个无限大的棋盘，棋盘上有一匹马，马移动的方式为日字型。
即假设马当前的位置为(x,y)，那么下一步可以移动到(x+1,y+2)，(x+1,y-2)，(x-1,y+2)，
(x-1,y-2)，(x+2,y+1)，(x+2,y-1)，(x-2,y+1)或者(x-2,y-1)这8个位置。
问马是否能从坐标(x,y)按照上述移动规则移动到坐标(x2,y2)。
Solution: 由于棋盘无限大，所以马能够到达任一位置。
为了证明这个结论，可以先画图证明马能够到达离它距离为1的上下左右四个位置。
然后依次向外扩展，就可以到达任一位置。
加强版是可以跳到(p,q)，当然对称的也可以跳到(q,p)。那么接下来是数学推导：
http://www.shuatiblog.com/blog/2014/08/15/Knight-tour-jumpable-question/
Read full article from [itint5]跳马问题加强版 - 阿牧遥 - 博客园
首先由跳马问题一，就是普通的日字型跳法，那么在无限棋盘上，任何点都是可达的。证法是先推出可以由(0,0)到(0,1)，那么由对称型等可知任何点都可以到了。
有一个无限大的棋盘，棋盘上有一匹马，马移动的方式为日字型。
即假设马当前的位置为(x,y)，那么下一步可以移动到(x+1,y+2)，(x+1,y-2)，(x-1,y+2)，
(x-1,y-2)，(x+2,y+1)，(x+2,y-1)，(x-2,y+1)或者(x-2,y-1)这8个位置。
问马是否能从坐标(x,y)按照上述移动规则移动到坐标(x2,y2)。
Solution: 由于棋盘无限大，所以马能够到达任一位置。
为了证明这个结论，可以先画图证明马能够到达离它距离为1的上下左右四个位置。
然后依次向外扩展，就可以到达任一位置。
加强版是可以跳到(p,q)，当然对称的也可以跳到(q,p)。那么接下来是数学推导：
1. 计算dx=x-x2,dy=y-y2。
2. 求出p,q的最大公约数g，如果dx或者dy不能被g整除，那么很显然无解。
3. 将p,q,dx,dy都除以g，现在p和q互质了。
4. 注意到马可以跳到点(0,2p)（先(p,q)跳一下，然后(p,-q)跳一下），重复这个过程，马可以跳到任意(0,2kp)的点，由于对称性，也可以跳到任意(2kp,0)的点。
5. 下面这一步很关键，由于p,q互质，那么存在x,y满足px+qy=1（扩展欧几里德定理）。这样，马可以跳到(0,2)和和(2,0)，由于对称性，马可以跳到任意坐标都为偶数点。[因为在一条线上可以前进2p和2q为单位，那么组合后可以到任意2n]
6. 有了上面的结论，其实只用考虑(0,0),(0,1),(1,0),(1,1)这4个点是否可达。(0,0)是可达的，(0,1)和(1,0)由于对称性只用考虑(0,1)。
7. 对于(1,1)，其实是永远可达的。如果q,p都为奇数，可以先跳到(1+p,1+q)的点（利用5中的结论），然后(-p,-q)跳到(1,1)。如果p,q一奇一偶，可以先跳到(1+p+q,1+q+p)的点（利用5中的结论），然后(-p,-q),(-q,-p)两步跳到(1,1)。[因为1+q和1+p都是偶数]
8. 对于(0,1)，如果p,q一奇一偶，那么也是永远可达的（同7可证）。如果p,q都是奇数，那么是不可能跳到(0,1)的，因为两个奇数不管怎么加减交替运算都不可能变成一奇一偶。[因为规则是p和q可以调换，所以根据奇偶性(0,1)可达。而全部是奇数，那么只能由(奇，奇)到(偶，偶)或反之]
所以最后的结论就是：第3步之后，如果p,q一奇一偶，那么可达。否则dx,dy同奇或同偶才可达。
2. 求出p,q的最大公约数g，如果dx或者dy不能被g整除，那么很显然无解。
3. 将p,q,dx,dy都除以g，现在p和q互质了。
4. 注意到马可以跳到点(0,2p)（先(p,q)跳一下，然后(p,-q)跳一下），重复这个过程，马可以跳到任意(0,2kp)的点，由于对称性，也可以跳到任意(2kp,0)的点。
5. 下面这一步很关键，由于p,q互质，那么存在x,y满足px+qy=1（扩展欧几里德定理）。这样，马可以跳到(0,2)和和(2,0)，由于对称性，马可以跳到任意坐标都为偶数点。[因为在一条线上可以前进2p和2q为单位，那么组合后可以到任意2n]
6. 有了上面的结论，其实只用考虑(0,0),(0,1),(1,0),(1,1)这4个点是否可达。(0,0)是可达的，(0,1)和(1,0)由于对称性只用考虑(0,1)。
7. 对于(1,1)，其实是永远可达的。如果q,p都为奇数，可以先跳到(1+p,1+q)的点（利用5中的结论），然后(-p,-q)跳到(1,1)。如果p,q一奇一偶，可以先跳到(1+p+q,1+q+p)的点（利用5中的结论），然后(-p,-q),(-q,-p)两步跳到(1,1)。[因为1+q和1+p都是偶数]
8. 对于(0,1)，如果p,q一奇一偶，那么也是永远可达的（同7可证）。如果p,q都是奇数，那么是不可能跳到(0,1)的，因为两个奇数不管怎么加减交替运算都不可能变成一奇一偶。[因为规则是p和q可以调换，所以根据奇偶性(0,1)可达。而全部是奇数，那么只能由(奇，奇)到(偶，偶)或反之]
所以最后的结论就是：第3步之后，如果p,q一奇一偶，那么可达。否则dx,dy同奇或同偶才可达。
注：扩展欧几里得定理:
对于与不完全为 0 的非负整数 a, b; gcd(a, b)表示 a，b 的最大公约数。那么存在唯一的整数 x，y 使得 gcd(a, b)=ax+by。互质时有px+qy=1。
int gcd(int a, int b) { return b ? gcd(b, a % b) : a;}bool canJump(int p, int q, int x, int y, int x2, int y2) { if (p == 0 && q == 0) return (x == x2) && (y == y2); int dx = x2 - x; int dy = y2 - y; int g = gcd(p, q); if (dx % g != 0 || dy % g != 0) return false; dx /= g; dy /= g; p /= g; q /= g; if ((dx - dy) % 2 == 0) return true; if ((p - q) % 2 != 0) return true; return false;}http://www.shuatiblog.com/blog/2014/08/15/Knight-tour-jumpable-question/
Read full article from [itint5]跳马问题加强版 - 阿牧遥 - 博客园
