Recursive grid traveling algorithm

Question

I'm trying to come up with a solution to a coding challenge on Kattis, where there is a 2D grid filled with x's and o's, and the goal is to figure out whether or not a given starting coordinate can reach a given end coordinate by traveling up, down, left, or right. Only the o's are navigable, and the width and height of the grid can each be up to 1000 characters.

Here is an example grid:

xoxxx
ooxxo
oxxxo
ooooo
oxxxx
ooooo

I'll define this as

std::vector<std::string> space;

For this space, e.g., space[0][1] can reach space[5][4].

Note: This isn't quite the problem. I've generalized it a bit because there are some nuances that are a bit irrelevant to efficiency. Here's the actual problem.

I've taken a recursive approach to this problem, and my program passes the first 22 out of the 25 total test cases, before exceeding the 1-second time limit. The algorithm that I thought of was to keep checking whether the next valid coordinate could reach the end. The base case occurs when the starting coordinate is the ending coordinate, and it signifies that the problem's starting point can reach the ending point. If there is no valid next location then the current path cannot reach the ending point. If all the paths reach a dead end then that signifies that the problem's starting point cannot travel to the ending point.

Here are the brains of the program (specifically canTravel):

struct Point {
    int x, y;
    friend bool operator==(const Point &p1, const Point &p2);
};

bool operator==(const Point &p1, const Point &p2) {
    return p1.x == p2.x && p1.y == p2.y;
}

std::vector<Point> memo; // take note of the visited locations to avoid revisiting them

bool memoContains(const Point &p1) {
    return std::find_if(memo.begin(), memo.end(), [&](const Point &p) { return p == p1; }) != memo.end();
}

bool canTravel(const std::vector<std::string> &space, const Point &start, const Point &end) {
    if (start == end) // base case: the start == the destination
        return true; 

    memo.push_back(start); // add current location to the list of visited locations

    /*
    format:

    const auto &next_location = avoid out of bounds error &&
        next location is an 'o' &&
        avoid revisiting a location &&
        recursively check whether the next location can reach the destination

    */

    const auto &right = start.x < space[start.y].length() - 1 && 
        space[start.y][start.x + 1] == 'o' && 
        !memoContains({ start.x + 1, start.y }) && 
        canTravel(space, { start.x + 1, start.y }, end);

    const auto &left = start.x > 0 && 
        space[start.y][start.x - 1] == 'o' && 
        !memoContains({ start.x - 1, start.y }) && 
        canTravel(space, { start.x - 1, start.y }, end);

    const auto &down = start.y < space.size() - 1 && 
        space[start.y + 1][start.x] == 'o' && 
        !memoContains({ start.x, start.y + 1 }) && 
        canTravel(space, { start.x, start.y + 1 }, end);

    const auto &up = p1.y > 0 && 
        space[start.y - 1][start.x] == 'o' && 
        !memoContains({ start.x, start.y - 1 }) && 
        canTravel(space, { start.x, start.y - 1 }, end);

    return right || left || down || up; // at least one path needs to reach the destination
}

Why is this slow/inefficient? How can it be improved? Can a recursive approach be used here or is an iterative one preferable?

Answer 1

What is killing your performance is memoContains. It turns your algorithm from O(n) into O(n^2).

The better solution is to create a second array of the same size as your input, where you mark each cell visited. Then you can do the check in O(1).

Next, you need to implement a short circuit for your logic. If right is true, there is no point in computing the other directions.

Why do you define right and the other three bools as references?

There are some more tricks you can apply, for example to avoid checking for out-of-bounds indexing by simply making the array one cell larger on all sides, and filling those positions with x.

Finally, regarding recursion. It's a nice way of describing the algorithm. You might get better performance if you use a stack instead. But the only way to know for sure is to try it out and time it. :)

Oh, and one more thing:

std::vector<std::string> space;

Is highly inefficient. Your data is all over the memory because the data for each array is allocated independently. You should probably make this a single vector (or string if you must) that you index as row * width + column. Note that now you can index neighboring cells using simple pointer arithmetic (add 1 to the pointer to access the cell on the right, for example).