Skip to content

Instantly share code, notes, and snippets.

@adrian17
Created April 10, 2015 12:14
Show Gist options
  • Save adrian17/2f3ac4e32fddc809c29a to your computer and use it in GitHub Desktop.
Save adrian17/2f3ac4e32fddc809c29a to your computer and use it in GitHub Desktop.
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
#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);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment