CR 164051 Revision 3

#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <vector>
#include <set>

using std::vector;

struct Point
{
    Point() {};

    Point(const int a, const int b) :
        x(a),
        y(b)
    {};

    Point(const Point &p) :
        Point(p.x, p.y)
    {};

    Point operator+(const Point &rhs)
    {
        Point lhs;

        lhs.x = x + rhs.x;
        lhs.y = y + rhs.y;

        return lhs;
    }

    bool operator<(const Point& rhs) const
    {
        return (x == rhs.x) ?
            y < rhs.y :
            x < rhs.x;
    }

    int x = 0;
    int y = 0;
};

class Matrix
{
public:
    Matrix(
        vector<vector<char>> m,
        vector<Point> d) :
        matrix(std::move(m)),
        directions(std::move(d)),
        input("")
    {};

    bool find_next_match(size_t index, Point cur_pos)
    {
        ++index;

        if (index > input.size() - 1)
        {
            return true;
        }

        used.insert(cur_pos);

        for (const auto &dir : directions)
        {
            Point new_pos(cur_pos + dir);

            if (new_pos.x < 0 ||
                new_pos.y < 0 ||
                new_pos.x > matrix.size() - 1 ||
                new_pos.y > matrix[0].size())
            {
                continue;
            }

            if (matrix[new_pos.x][new_pos.y] != input[index])
            {
                continue;
            }

            if (used.count(new_pos))
            {
                continue;
            }

            if (find_next_match(index, new_pos))
            {
                return true;
            }
        }

        used.erase(cur_pos);

        return false;
    }

    bool exists(const std::string &s)
    {
        input = s;

        for (size_t m = 0; m < matrix.size(); ++m)
        {
            for (size_t n = 0; n < matrix[0].size(); ++n)
            {
                if (matrix[m][n] == input[0])
                {
                    used.clear();
                    if (find_next_match(0, Point(m, n)))
                    {
                        return true;
                    }
                }
            }
        }

        return false;
    }

private:
    vector<vector<char>> matrix;
    vector<Point> directions;
    std::set<Point> used;
    std::string input;
};

int main (int argc, char **argv)
{
    Matrix m(
    {
        {'A', 'B', 'C', 'E'},
        {'S', 'F', 'C', 'S'},
        {'A', 'D', 'E', 'E'},
    },
    {
        Point(-1, 0),
        Point(0, 1),
        Point(1, 0),
        Point(0, -1),
    });

    std::ifstream infile(argv[1], std::ios::in | std::ifstream::binary);

    std::string line;
    while (infile.good() && getline(infile, line))
    {
        std::cout << (m.exists(line) ? "True" : "False") << "\n";
    }
}