250Point:
由坐标(0, 0),通过类似马步的走法,判断能不能到达(x, y),其中,马步的间隔由题目给出,例如,间隔为n,则从坐标(0, 0)出发,一步可到达(n, 1), (n, -1), (1, n), (-1, n), (-n, 1), (-n, -1), (1, -n), (-1, -n)。
分析:开始时,这个题我想复杂了,本来想枚举+BFS,后来稍微分析下,就可以得到结论。(xE表示任意偶数X坐标,xO表示任意奇数X坐标,Y坐标类似。nEven表示任意偶数间隔,nOdd表示任意奇数间隔)
1. 从坐标(0, 0)出发,通过(0, 0) -> (1, n) -> (2, 0) .... 可以到达(xE, 0)。通过(0, 0) -> (n, 1) -> (0, 2).... 可以到达(0, yE)。所以通过坐标(0, 0)可以到达(xE, yE)。
2. 在1的基础上:
(1) 当马步间隔集合中存在至少一个偶数间隔nEven时:
由1知(xE, yE)可达。
(xO, yE)可达,通过(xE' + 1, yE' + nEven)。
(xE, yO)可达,通过(xE' + nEven, yE' + 1)。
(XO, YO)可达,通过(xO' + nEven, yE' + 1)或者(xE' + 1, yO' + nEven)。
(2) 当马步间隔集合中不存在偶数间隔时:
由1知(xE, yE)可达。
(xO, yE)和 (xE, yO)均不可达,因为通过(xE', yE')只能到达(XO‘, YO’)。
(XO, YO)可达,通过(xE' + nOdd, yE' + 1)或者(xE' + 1, yE' + nOdd)。
总结:当马步间隔集合中存在至少一个偶数间隔nEven时,任意坐标(x, y)可达,当马步间隔集合中不存在偶数间隔时,只有(xE, yE)和(xO, yO)可达。
posted on 2011-08-10 14:17
Lshain 阅读(93)
评论(0) 编辑 收藏 引用 所属分类:
TopCode SRM