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 阅读(94)
评论(0) 编辑 收藏 引用 所属分类:
TopCode SRM