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

Here's what the whole grid looks like as an image:

The black squares are inaccessible, white accessible, gray accessible and reachable by movement from the center. There's a 600x600 bounding box of black because the digits of 299 add to 20, so we only have to consider that.

This exercise is basically a "flood fill", with a shape which is just about the worst case possible for a flood fill. You can do the symmetry speedup if you like, though that's not really where the meat of the issue is--my solution runs in 160 ms without it (under 50ms with it).

The big speed wins are (1) do a line-filling flood so you don't have to put every point on the stack, and (2) manage your own stack instead of doing recursion. I built my stack as two dynamically-allocated vectors of ints (for x and y), and they grow to about 16k, so building whole stack frames that deep would definitely be a huge loss.