[原创]象棋遍历问题

技术员

[这个贴子最后由技术员在 2009/07/11 10:35am 第 1 次编辑]

[watermark]中国象棋的马能在10x9的格子上遍历到每个点。但可不可能在MxN的格子上遍历不到某些点。比如M=10,N=10.[/watermark]
现在要求马在每格上只能经过一次，不能重复。

fleurly

下面引用由技术员在 2009/06/29 07:40am 发表的内容：
(水印部分不能引用)

我记得学数据结构的时候见过这个题目
写算法的

白新岭

当2*2个方格时，中心点不能跳到。当为n*m形式的数，积大于等于6，n,m都大于1时，应该是马能到任何位置。

技术员

下面引用由白新岭在 2009/07/01 09:03am 发表的内容：
当2*2个方格时，中心点不能跳到。当为n*m形式的数，积大于等于6，n,m都大于1时，应该是马能到任何位置。

可以证明吗？请问陆教授他的回答对吗。

wanwna

发散发散你的数学思维，这个问题其实很容易证明。

技术员

下面引用由wanwna在 2009/07/01 10:40pm 发表的内容：
发散发散你的数学思维，这个问题其实很容易证明。

我觉得较难。还看你的证明吧。

wanwna

很简单. 对于m>5,n>5的棋盘,坐标 对于上面任意一点,(x,y) (1<=x<=m-1,1<=y<=n) 现在考虑可否到达(x+1,y), 如果x(x+2,y+1)->(x,y+2)->(x,y) 如果x>=m-1,y(x-2,y+1)->(x,y+2)->(x,y) 如果x=n-1,可以选择路线 (x,y)->(x+2,y-1)->(x,y-2)->(x,y) 如果x>=m-1,y>=n-1,可以选择路线 (x,y)->(x-2,y-1)->(x,y-2)->(x,y) 于是任意(x,y)可以走到(x+1,y) 同理,任意(x,y)可以走到(x-1,y),(x,y+1),(x,y-1)(只要在棋盘内) 于是,从棋盘任意一点出发,可以到达棋盘上任何一点

技术员

你的证明我没看懂。但你的意思是对于M>5与N>5,都可以遍历到。和3楼答案不同。到底是你错还是他错。你能说清楚吗？

wanwna

不是谁对谁错的问题，我的意思只是棋盘足够大的意思。其实6x6可能并非最小的,但达到6x6就一定可以满足马走到任意位置。
我的意思是，无论马在棋盘上的哪一点，都可以有手段往上下左右走一格，于是马就可以到任何地方了。

技术员

如果考虑这个问题。如果M与N其中一个小于6.又是什么情况呢？