algorithm - Improve the solution to monkey grid puzzle

Question

I was trying to solve the following problem:

There is a monkey which can walk around on a planar grid. The monkey can move one space at a time left, right, up or down. That is, from (x, y) the monkey 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 absolute value of the x coordinate plus the sum of the digits of the absolute value of the y coordinate are lesser than or equal to 19 are accessible to the monkey. For example, the point (59, 79) is inaccessible because 5 + 9 + 7 + 9 = 30, which is greater than 19. Another example: the point (-5, -7) is accessible because abs(-5) + abs(-7) = 5 + 7 = 12, which is less than 19. How many points can the monkey access if it starts at (0, 0), including (0, 0) itself?

I came up with the following brute force solution (pseudo code):

/*
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();
}
*/

This is a very brute force solution. One of the optimizations I used was to one scan one quadrant instead of looking at four. Another one was to ignore the points that we've already seen before.

However, looking at the final points, I was trying to find a pattern, perhaps a mathematical solution or a different approach that would be better than what I came up.

Any thoughts ?

PS: If you want, I can post the data somewhere. It is interesting to look at it with any one of the axis sorted.

First quadrant visual:

Answer 1

这是整个网格作为图像的样子：

黑色方块是不可接近的，白色方块是可接近的，灰色方块是可通过从中心移动到达的。有一个 600x600 的黑色边界框，因为 299 的数字加到 20，所以我们只需要考虑这一点。

这个练习基本上是一个“洪水填充”，其形状几乎是洪水填充的最坏情况。如果您愿意，您可以进行对称加速，尽管这并不是问题的关键所在——我的解决方案在没有它的情况下运行时间为 160 毫秒（在 50 毫秒以下）。

最大的速度优势是（1）进行行填充洪水，因此您不必将每个点都放在堆栈上，以及（2）管理自己的堆栈而不是进行递归。我将堆栈构建为两个动态分配的整数向量（用于 x 和 y），它们增长到大约 16k，因此构建这么深的整个堆栈帧肯定会是一个巨大的损失。

Answer 2

在没有寻找理想解决方案的情况下，我有类似的东西。对于猴子所在的每一点，我将接下来的 4 种可能性添加到列表中，并且仅在没有被访问过的情况下递归地对接下来的 4 种可能性进行相同操作。这也可以通过多处理来加快处理速度。

Answer 3

我不确定这与 Brainydexter 的想法有什么不同...漫游一个象限，我建立了一个数组哈希(index = 299 * y + x)并用另一个数组构建了结果，每个索引只存储从其先前索引扩展的点，例如：

first iteration, result = [[(0,0)]]
second iteration, result = [[(0,0)],[(0,1),(1,0)]]
...

在 JavaScript 中的旧 IBM Thinkpad 上，速度似乎在 35-120 毫秒之间变化（在这里摆弄）。

Answer 4

这是我的解决方案，更像是 BFS：

int DigitSum(int num)
{
    int sum = 0;

    num = (num >= 0) ? num : -num;
    while(num) {
        sum += num % 10;
        num /= 10;
    }
    return sum;
}

struct Point {
    int x,y;
    Point(): x(0), y(0) {}
    Point(int x1, int y1): x(x1), y(y1) {}

    friend bool operator<(const Point& p1, const Point& p2)
    {
        if (p1.x < p2.x) {
            return true;
        } else if (p1.x == p2.x) {
            return (p1.y < p2.y);
        } else {
            return false;
        }
    }
};

void neighbor(vector<Point>& n, const Point& p)
{
    if (n.size() < 4) n.resize(4);

    n[0] = Point(p.x-1, p.y);
    n[1] = Point(p.x+1, p.y);
    n[2] = Point(p.x, p.y-1);
    n[3] = Point(p.x, p.y+1);
}

int numMoves(const Point& start)
{
    map<Point, bool> m;
    queue<Point> q;
    int count = 0;
    vector<Point> neigh;

    q.push(start);
    m[start] = true;
    while (! q.empty()) {
        Point c = q.front();
        neighbor(neigh, c);
        for (auto p: neigh) {
            if ((!m[p]) && (DigitSum(p.x) + DigitSum(p.y) <= 19)) {
                count++;
                m[p] = true;
                q.push(p);
            }
        }
        q.pop();
    }
    return count;
}