int isexist;

TrieNode* next[26];

TrieNode() {

fill(next, next+26, nullptr);

isexist = -1;

}

~TrieNode() {

for (int i = 0; i < 26; ++i)

if (next[i]) delete next[i];

}

int arr[4][2] = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}}; // 四个搜索方向

void insert(TrieNode* root, const string& s, int& index) {

int n = s.size();

for (int i = 0; i < n; ++i) {

int idx = s[i] - 'a';

if (!root->next[idx]) root->next[idx] = new TrieNode();

root = root->next[idx];

}

root->isexist = index;

}

void dfs(int r, int c, TrieNode* root, unordered_set<int>& res, vector<vector<char>> b) {

b[r][c] = '0'; // 走过的地方标记为0

if (root && root->isexist) res.insert(root->isexist);

for (int i = 0; i < 4; ++i) {

int newr = r + arr[i][0], newc = c + arr[i][1];

if (newr >= 0 && newc >= 0 && newr < b.size() && newc < b[0].size() && b[newr][newc] != '0' && root->next[b[newr][newc]-'a']) {

dfs(newr, newc, root->next[b[newr][newc] - 'a'], res, b);

}

}

}

vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {

TrieNode* root = new TrieNode();

int n = words.size();

for (int i = 0; i < n; ++i) {

insert(root, words[i], i);

}

unordered_set<int> res; // 保存board中查到到的word序号

for (int r = 0; r < board.size(); ++r) {

for (int c= 0; c < board[r].size(); ++c) {

if(root->next[board[r][c]-'a'])dfs(r,c,root->next[board[r][c]-'a'],res,board);

}

}

vector<string>ress;//根据res中的序号制作string数组返回

for(auto it:res){

ress.push_back(words[it]);

}

return ress;

}