Recursive grid traveling algorithm
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&lt;std::string&gt; 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).