input.txt

6 1 1
T H T L E D 
P E N U R G
I G S D I S
Y G A W S I 
W H L Y N T
I T A R G I

main.cpp

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

struct Node
{
	bool end;
	Node *ptrs[26];
};

void load(Node &startNode)
{
	std::ifstream f("enable1.txt");
	std::string word;
	while (f >> word) {
		Node *node = &startNode;
		for (char c : word) {
			int i = ::toupper(c) - 'A';
			if (!node->ptrs[i])
				node->ptrs[i] = new Node();
			node = node->ptrs[i];
		}
		node->end = true;
	}
}

void cleanup(Node &node)
{
	for (Node* ptr : node.ptrs)
		if (ptr) {
			cleanup(*ptr);
			delete ptr;
		}
}

typedef std::vector<std::vector<char>> WordMap;
typedef std::vector<std::pair<int, int>> Path;

bool solve(Path &path, Path &spaces, Node *node, Node *startNode, const WordMap &map, int x, int y, int W, int H)
{
	char c = map[x][y];
	node = node->ptrs[c - 'A'];
	if (!node)
		return false;
	if (path.size() == W * H)
		if (node->end)
			return true;
		else
			return false;

	static const std::pair<int, int> dirs[4] = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
	for (const auto &dir : dirs) {
		int new_x = x + dir.first, new_y = y + dir.second;
		if (new_x < 0 || new_x >= W || new_y < 0 || new_y >= H)
			continue;
		if (std::find(path.begin(), path.end(), std::make_pair(new_x, new_y)) != path.end())
			continue;
		path.emplace_back(new_x, new_y);
		if(solve(path, spaces, node, startNode, map, new_x, new_y, W, H))
			return true;
		if (node->end) {
			spaces.emplace_back(new_x, new_y);
			if(solve(path, spaces, startNode, startNode, map, new_x, new_y, W, H))
				return true;
			spaces.pop_back();
		}
		path.pop_back();
		
	}
	return false;
}

int main()
{
	Node startNode {};
	load(startNode);

	std::ifstream f("input.txt");
	int W, H, x, y;
	f >> H >> x >> y;
	f.ignore();
	std::string line;
	WordMap map;
	while (std::getline(f, line)) {
		std::istringstream ss(line);
		char c;
		map.emplace_back();
		while (ss >> c)
			map.back().emplace_back(c);
	}
	W = map[0].size();
	x -= 1; y -= 1;

	Path spaces, path = {{x, y}};
	solve(path, spaces, &startNode, &startNode, map, x, y, W, H);

	for (auto xy : path) {
		if (std::find(spaces.begin(), spaces.end(), xy) != spaces.end())
			std::cout << " ";
		std::cout << map[xy.first][xy.second];
	}

	cleanup(startNode);
}