Determine whether an array S appear in a matrix A

std::tuple<int,char> mytuple (10,'a');

  std::get<0>(mytuple) = 20;

if S appears in A, there is a path.

This problem is about how to store the path already visited.

Naive thinking is to store 4 directions, since for each A[i][j], it has four neighbor to traversal. and there are 4! possiblities.

Clever way is to store a tuple {i, j, idx} where idx is the element position in S. 

and do four direction recursive.

When the tuple is in the set, means this element has been detected before.

Hence this result in a complexity of O(MNL) where M*N is the matrix size and L is the length of S.

C++: tuple initialization

 tuple tmp(i,j,len);

Solution:

class HashTuple
{
public:
    size_t operator() (const tuple &t) const
    {
        return hash()(get<0>(t)) ^ hash()(get<1>(t)) ^ hash()(get<2>(t)) ;
    }
};

bool match_helper(const vector > &A, const vector &S, unordered_set, HashTuple> cache,
                  int i, int j, int len)
{
     if (S.size()==len)  return true;

     tuple tmp(i,j,len);

     if (i<0 i="">=A.size() || j<0 j="">=A.size() || cache.find( tmp )!= cache.cend())
            return false;

     if (A[i][j] == S[len] && (match_helper(A, S, cache, i-1, j, len+1) ||
                               match_helper(A, S, cache, i+1, j, len+1) ||
                               match_helper(A, S, cache, i, j-1, len+1) ||
                               match_helper(A, S, cache, i, j+1, len+1) ))
                                return true;
    cache.insert(tmp);
    return false;
}

bool match(const vector > &A, const vector &S)
{
    unordered_set, HashTuple> cache;
    for (int i=0; i