哪位大侠能拔下这一城？

方诺

There is an ant which can walk around on a planar grid. The ant can move one space at a time left, right, up or down. That is, from (x, y) the ant can go to (x+1, y), (x-1, y), (x, y+1), and (x, y-1). Points where the sum of the digits of the x coordinate plus the sum of the digits of the y coordinate are greater than 25 are inaccessible to the ant. For example, the point (59, 79) is inaccessible because 5 + 9 + 7 + 9 = 30, which is greater than 25. How many points can the ant access if it starts at (1000, 1000), including (1000, 1000) itself?

666

蚂蚁在我头皮上乱爬。

调皮鬼

没做出来。
应该不会超过1459763吧。

昨夜雨

243603？

昨夜雨

5# AprilFool

阿福怎么跑到我的楼下去了？

楼主说了，蚂蚁只能一格一格地爬，而且不能到999这样的格子里。所以蚂蚁不会从楼上（1000）跳到楼下（999）。:)

昨夜雨

5# 昨夜雨

阿福跑了！！！！追！

tieshu

201

昨夜雨

铁树，It starts at (1000, 1000).

It can't walk down to (1000, 999) or (999, 1000).  On the other hand, if it walks along one straight line, it can pass points of (1000, 1001), (1000, 1002), ... (1000, 1201) easily.  And there are 201 points already.  And obviously it has not hit the boudary yet. :)

tieshu

8# 昨夜雨
哈哈，是我审题错误，打倒方诺！

AprilFool

5# 昨夜雨

阿福跑了！！！！追！


昨夜雨 发表于 2009-5-28 11:00 AM

Now you see me......now you don't! 哈哈，把站长溜晕乎了吧。

开始分析得太不仔细，出帖后发现自己忽视了很多在中间的点。现在没时间仔细算，晚上吧。如果我算出来，结果可能跟站长的差不多。

铁树的图画得好漂亮啊。怎么画的？能教教我吗？

昨夜雨

10# AprilFool

其实我也还没有算出准确的数字。:)

昨夜雨

11# 昨夜雨

把解题思路再过滤一遍。然后写个循环程序，得出的答案是230167。

tieshu

我这个就是用程序算出来的，不行，我也糊涂了！

tieshu

花了九牛二虎之力用xls画出来的，因为hit到xls的奇点，居然总画不出来。
我的程序还是Loop的起始值没设好的原因。我觉得这不应该是一个很大数字:-)

Now you see me......now you don't! 哈哈，把站长溜晕乎了吧。

开始分析得太不仔细，出帖后发现自己忽视了很多在中间的点。现在没时间仔细算，晚上吧。如果我算出来，结果可能跟站长的差不多。

铁树 ...
AprilFool 发表于 2009-5-28 04:55 PM

tieshu

OK， my latest answer is 43050.
Attatched data file here. The Excel can't handle so many data point in one plot:-(

昨夜雨

15# tieshu

等方老师来打分吧！:)

tieshu

After considering the symmetry, my answer is 71047

方诺

嘿，我也没答案。

一个小朋友考我的题。不是来集思广益来了？

tieshu

OK, my final answer: 15681, with a visual picture, it is easier to judge the results

tieshu

The boundary points are:
1000,1698
1001,1598
1002,1498
1003,1398
1004,1298
1005,1198
.......
1048,1038
1038,1048
......
1198,1005
1298,1004
1398,1003
1498,1002,
1598,1001
1698,1000

八月风

边界为什么不可以是：1000，1797；1000，1896；1000，1995；等等？以此类推。。。。。。

tieshu

如果你把这些点在坐标上画出来，它们跟其它的点不能按题目给出的条件“连”在一起。

边界为什么不可以是：1000，1797；1000，1896；1000，1995；等等？以此类推。。。。。。
八月风 发表于 2009-5-29 10:16 AM

八月风

1000，1797点可以和1001，1796点连着；然后1002，1795点，等等；1000，1995点可以和1001，1994点连着，以此类推，应该符合题目的条件啊。

tieshu

这个题目的有趣之处就在于条件简单，而且满足这些条件的点阵在整个平面不是唯一的。根据不同的起始点，会有不同的答案和算法。

昨夜雨

18# 方诺

方老师不肯给出答案，肯定是我们没有算对。:)

这回把数据plot出来。答案是148848。

昨夜雨

21# 八月风

1000，1797不合条件。过不去。

昨夜雨

20# tieshu

1001,1598不是边界。蚂蚁可以按照下面的路径绕过（1001，1599），到达（1001，1600）以及以后的符合条件的点。

1000，1598
1000，1599
1000，1600
1001，1600
1001，1601

八月风

为什么呢？一路沿着1000的坐标线一格格过去不就行了?

21# 八月风

1000，1797不合条件。过不去。
昨夜雨 发表于 2009-5-29 10:48 AM

tieshu

嗯，这个正是我拿不准的地方，边界条件比我想得要复杂。你的图里的符号各代表什么意思？

20# tieshu

1001,1598不是边界。蚂蚁可以按照下面的路径绕过（1001，1599），到达（1001，1600）以及以后的符合条件的点。

1000，1598
1000，1599
1000，1600
1001，1600
1001，1601 ...
昨夜雨 发表于 2009-5-29 10:52 AM

昨夜雨

28# 八月风

铁树前面说了，“1000,1698”是边界，到头了。

昨夜雨

嗯，这个正是我拿不准的地方，边界条件比我想得要复杂。你的图里的符号各代表什么意思？


tieshu 发表于 2009-5-29 10:07 AM

左边的4位数字是坐标（从小到大）。

右边的代码其实也是坐标，但还有如下含义：

数字1-6：百位数（x100）。
零（0）十位数。
叉（x）个位数为1-9的点。

以上都是有效的点。

其余的点（.）是过不去的，或者不合条件的。反正是不算的。

所以最大的区域在(1000,1000)和（1698，1698）之间。

八月风

看大家解题，又多明白了一点。就象风雨说的，1000，1698是边界，但1001，1697应该是第二个边界吧？然后依此类推？

The boundary points are:
1000,1698
1001,1598
1002,1498
1003,1398
1004,1298
1005,1198
.......
1048,1038
1038,1048
......
1198,1005
1298,1004
1398,1003
1498,1002,
1598,1001
1698,1000
tieshu 发表于 2009-5-29 09:35 AM

四维

里边还有点不符合要求： （1001，1689）

看大家解题，又多明白了一点。就象风雨说的，1000，1698是边界，但1001，1697应该是第二个边界吧？然后依此类推？


八月风 发表于 2009-5-29 02:43 PM

八月风

（1001，1697）是1001这条线的边界，但是这条线上有些点要去除掉，比如（1001，1689），（1001，1599）。
然后1002这条线的边界是1696，但中间要去掉（1002，1689），（1002，1688），（1002，1679），（1002，1599），（1002，1598），（1002，1589），（1002，1499）等等。我这样的思路对不对？

昨夜雨

34# 八月风

虽然现在没错，但不完整。以后有可能出错。

比如说，你推算一下，x=1020时，y的边界点在哪里？1588? 1597? 1678? (1020,1590)...(1020,1597)之间，算不算有效点？

八月风

我是顺着X恒定的线来的，所以X=1003时，Y的最大边界是1695，中间要去掉的点的Y值是：1689，1688，1687，1679，1678，1669，1599，1598，1597，1589，1588，1579，1499，1498，1489，1399。对比一下X=1002的结果和X=1003的结果，实际上是很有规律可循的。有规律就不怕会出错了。:)

昨夜雨

36# 八月风

OK. 你的结果可能是230167。我的第二个答案可能就是这样算出来的。

八月风

按照上面的规律，X=1000到X=1009都应该能顺利推算出来，但到X=1010时，就有些变化了。你出的题道理应该是一样的，Y=1090时的规律和Y=1009的规律不完全一样。

这道题可能还是写程序来算容易些，否则要花点时间，但应该能解得出来。

tieshu

风雨这个plot做的太漂亮了！用wordpad打开，把font缩小，可以很容易检查结果的正确与否。我没查出错误来

这样看来，是不是要走两遍？第一遍找出所有满足条件的点，存到这个文件里。第二遍来数这个文件里满足条件的点。因为一遍做下来很容易产生重复点。我昨天试着存在memory里，结果非常慢，就gave up了，因为一直把这个题目看成是一个小巧秀气的问题

18# 方诺

方老师不肯给出答案，肯定是我们没有算对。:)

这回把数据plot出来。答案是148848。
昨夜雨 发表于 2009-5-29 10:45 AM

tieshu

哈哈，又想了一下，稍稍改一下我的程序，应该一遍可以走下来。
这条线让俺赚了不少分，也exercise了脑子

昨夜雨

39# tieshu

因为循环可以是从上到下然后从左到右，所以每次找到一个符合条件的格点，就可以和已经确认的格点（左边或者上边）进行相邻检验。如果左边或者上边的格点已经被确认，那么就算通过相邻检验，加入内存。这样可以一次性完成。

tieshu

我按这样算出来的是228095，我觉得这个数字没有排除在1698x1698范围内的孤岛点阵。
所以想一次过关还是有问题。

昨夜雨

42# tieshu

恐怕你累计数字的时候出错了。整个有效面积不会大于699x699的一半。

tieshu

我这个数据不是题目要求的，而是在1698x1698范围内，所有满足条件的点阵，但并不保证所有点都连在一起。我觉得一遍做下来，还是很难判定一个点是否和（1000，1000）有联系。这大概是这道题的难点。
借助plot，我们很容易判定（1000，1699）到（1699， 1000)这条线是分界线，在这条线外的点不用数。

tieshu

OK, new result after cutting the line with (1000,1698) to (1698, 1000）:
159971
See the map.zip

tieshu

我对比了一下map1.zip和map.zip, 确认（1000，1698），（1698，1000），右下方的点和起点没有链接。

昨夜雨

45# tieshu

这一组的答案更好些。现在还有些孤岛，比如（1020,1591）到（1020，1597）之间的格点，虽然在数值上合法，但没有相邻点。

tieshu

谢谢风雨指导，终于得到了和你相同的答案：148848

关键在于保存前一排(y-1)所有点和同一排前一个点(x-1)的状态，这样在validate任意点的时候就有了一个固定的参考系。

赶快把方老师扶起来，谢谢你出题让我赚了不少分。
周末愉快！

昨夜雨

48# tieshu

我贤弟那边也有人算出148848的答案。

不过据说还有更简便的推算法。先让方老师躺着说也可以。:)

方诺

就是觉得应该有更好的方法。听说是面试题，不会那么复杂。