改进猴子网格拼图的解决方案

Question

我试图解决以下问题:

有一只猴子可以在平面网格上走动.猴子可以一次向左,向右,向上或向下移动一个空间.也就是说,从(x,y)猴子可以到(x + 1,y),(x-1,y),(x,y + 1)和(x,y-1).猴子可以访问其中x坐标的绝对值的数字之和加上y坐标的绝对值的数字之和小于或等于19的点.例如,点(59,79)是不可访问的,因为5 + 9 + 7 + 9 = 30,大于19.另一个例子:点(-5,-7)是可访问的,因为abs(-5)+ abs(-7)= 5 + 7 = 12,小于19.如果从(0,0)开始,猴子可以访问多少个点,包括(0,0)本身？

我想出了以下蛮力解决方案(伪代码):

/*
legitPoints = {}; // all the allowed points that monkey can goto
list.push( Point(0,0) ); // start exploring from origin

while(!list.empty()){
 Point p = list.pop_front(); // remove point

 // if p has been seen before; ignore p => continue;
 // else mark it and proceed further

 if(legit(p){
 // since we are only exploring points in one quadrant, 
 // we don't need to check for -x direction and -y direction
 // hence explore the following: this is like Breadth First Search
  list.push(Point(p.x+1, p.y)); // explore x+1, y
  list.push(Point(p.x, p.y+1)); // explore x, y+1

  legitPoints.insert(p); // during insertion, ignore duplicates 
                         // (although no duplicates should come through after above check)
                         // count properly using multipliers
                         // Origin => count once x = 0 && y == 0 => mul : 1
                         // X axis => count twice x = 0 && y != 0 => mul : 2
                         // Y axis => count twice x != 0 && y = 0 => mul : 2
                         // All others => mul : 4
 }

 return legitPoints.count();
}
*/

这是一个非常强力的解决方案.我使用的一个优化是扫描一个象限而不是看四个.另一个是忽略我们以前见过的观点.

然而,看着最后一站,我试图找到一种方式,也许是数学解或采用不同的方法,这将是更好的比我走了过来.

有什么想法吗 ？

PS:如果你愿意,我可以在某处发布数据.用任何一个轴排序来看它是很有趣的.

第一象限视觉:

Answer 1

以下是整个网格作为图像的样子:

黑色方块不可访问,白色可访问,灰色可访问,并可通过从中心移动到达.有一个600x600的黑色边界框,因为299的数字增加到20,所以我们只需要考虑.

这个练习基本上是一个"洪水填充",其形状几乎是洪水填充的最坏情况.如果你愿意,你可以做对称加速,虽然这不是问题的关键所在 - 我的解决方案在没有它的情况下运行160毫秒(50毫秒以下).

最大的速度胜利是(1)做一个填充线的洪水,所以你不必把每个点放在堆栈上,(2)管理你自己的堆栈而不是递归.我将我的堆栈构建为两个动态分配的整数向量(对于x和y),并且它们增长到大约16k,因此构建整个堆栈帧的深度绝对是一个巨大的损失.