Grid walk problem and solving it recursively

On CodeEval, there's a Grid Walk challenge:


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?

The first solution that came to my mind, intuitively, is to walk possible points recursively, breadth-first. Like this:

var monkey = function (x, y) {
    if (isPointAllowed(x, y) && !isPointVisited(x, y)) {
        visited.push({x: x, y: y});
        return 1 + monkey(x - 1, y) + monkey(x + 1, y) + monkey(x, y - 1) + monkey(x, y + 1);
    } else {
        return 0;
    }
};

So I return the count of current point and all adjacent points recursively, checking each point that it's allowed by game rules and hasn't been visited before. First is that the sum of the digits of x and y is less or equal 19; second is that the point isn't in visited array. The complete code is like:

```
var visited = [];

var isPointAllowed = function (x, y) {
var o = 0;
for (var i = 0, x = Math.abs(x), s = x.toString(), l = s.length; i < l; o += +s[i++]);
for (var i = 0, y = Math.abs(y), s = y.toString(), l = s.length; i < l; o += +s[i++]);
return o <= 19;
};

var isPointVisited = function (x, y) {
for (var i = 0; i < visited.length; i++) {
if (visited[i].x == x && visited[i].y == y)
return true;
}

return false;
};

var monkey = function (x, y) {
if (isPointAllowed

Profiling the code has shown that iterative search in sequential array (integer keys 0, 1, ...) is far slower that simply accessing a value by string key in an associative array of non-sequential keys represented by strings (like '-1,1' or similar). So I modified isPointVisited function:

var isPointVisited = function (x, y) {
    // console.log('isPointVisited, x = %s, y = %s', x, y);
    if (visited[[x, y]])
        return true;

    return false;
};

and monkey function:

var monkey = function (x, y) {
    if (isPointAllowed(x, y) && !isPointVisited(x, y)) {
        visited[[x, y]] = true;
        return 1 + monkey(x - 1, y) + monkey(x + 1, y) + monkey(x, y - 1) + monkey(x, y + 1);
    } else {
        return 0;
    }
};

This code still executes for a bit longer than 10 seconds (11800 ms on CodeEval) but it's at least 8 times faster than before.

StackExchange Code Review Q#82293, answer score: 3