class Solution {
public:
    struct Trie {
        array<shared_ptr<Trie>, 26> children;
        int ind;
        Trie(int i) : ind(i) {}
    };
    unordered_set<int> res;

    void addWord2Trie(const string& w, int i, int x, Trie* node) {
        if (i >= w.size()) {
            node->ind = x;
            return;
        }
        if (!node->children[w[i]-'a'])
            node->children[w[i]-'a'].reset(new Trie(-1));
        addWord2Trie(w, i+1, x, node->children[w[i]-'a'].get());
    }

    // to test that the word is in the trie
    bool isWordInTree(const string& w, Trie* node) {
        int i = 0;
        while (i < w.size() && node->children[w[i] - 'a'] != nullptr) {
            node = node->children[w[i] - 'a'].get();
            ++i;
        }
        cout <<  w << " " << node->ind << " " << i << endl;
        if (node->ind != -1 && i == w.size())
            return true;
        return false;
    }

    void dfs(int i, int j, vector<vector<char>>& board, vector<vector<bool>>& visited, Trie* node) {
        if (i < 0 || i >= board.size() || j < 0 || j >= board[0].size())
            return;
        if (visited[i][j])
            return;
        Trie* next = node->children[ board[i][j]-'a' ].get();
        visited[i][j] = true;
        if (next) {
            res.insert(next->ind);
            dfs(i+1, j, board, visited, next);
            dfs(i, j+1, board, visited, next);
            dfs(i-1, j, board, visited, next);
            dfs(i, j-1, board, visited, next);
        }
        visited[i][j] = false;
    }

    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        shared_ptr<Trie> trieRoot(new Trie(-1));
        for (int x = 0; x < words.size(); ++x)
            addWord2Trie(words[x], 0, x, trieRoot.get());
        //for (int x = 0; x < words.size(); ++x)
        //    cout << isWordInTree(words[x], trieRoot.get()) << endl;

        vector<vector<bool>> visited(board.size(), vector<bool>(board[0].size(), false));
        for (int i = 0; i < board.size(); ++i)
            for (int j = 0; j < board[i].size(); ++j) {
                for (int ii = 0; ii < board.size(); ++ii)
                    for (int jj = 0; jj < board[0].size(); ++jj)
                        visited[ii][jj] = false;
                dfs(i, j, board, visited, trieRoot.get());
            }

        vector<string> r;
        for (int i : res)
            if (i != -1)
                r.push_back(words[i]);
        return r;
    }
};