Untitled

class trienode{
    public:
    vector<trienode*> child;
    bool is_word;
    trienode(){
        is_word=false;
        child=vector<trienode*> (26,NULL);
    }
};

class trie{
    public:
    trienode* root;

    trienode* getroot(){ return root;}
    trie(vector<string>&words){
        root = new trienode();
        for(auto word:words) addword(word);
    }

    void addword(string &word){
        int k=0;
        trienode* cur=root;
        for(auto i:word){
            int k=i-'a';
            if(!cur->child[k]) cur->child[k]=new trienode();
            cur=cur->child[k];
        }
        cur->is_word=true;
    }
};


class Solution {
public:
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        trie* mt =new trie(words);
        trienode* root = mt->getroot();
        set<string> res;
        vector<vector<bool>> vis(board.size(),vector<bool>(board[0].size(),false));
        for(int i=0;i<board.size();i++){
            for(int j=0;j<board[0].size();j++){
                string path="";
                dfs(board,i,j,root,path,res,vis);
            }
        }
        vector<string> ans;
        for(auto i:res) ans.push_back(i);
        return ans;
    }

    void dfs(vector<vector<char>>& board,int x,int y,trienode* root,string path,set<string>&res,vector<vector<bool>> &vis){
        if(x<0||x>=board.size()||y<0||y>=board[0].size()|| vis[x][y] || !root->child[board[x][y]-'a']) return;

        vis[x][y]=1;
        path+=board[x][y];
        root = root->child[board[x][y]-'a'];
        if(root->is_word) {
            res.insert(path);
            root->is_word=false;
        }
        dfs(board,x+1,y,root,path,res,vis);
        dfs(board,x,y+1,root,path,res,vis);
        dfs(board,x-1,y,root,path,res,vis);
        dfs(board,x,y-1,root,path,res,vis);
        vis[x][y]=0;
        //path.pop_back();
    }
};