80 lines
2.3 KiB
C++
80 lines
2.3 KiB
C++
#include <iostream>
|
|
#include <cstring>
|
|
#include <string>
|
|
#include <unordered_map>
|
|
#include <set>
|
|
#include <vector>
|
|
#include <algorithm>
|
|
|
|
using namespace std;
|
|
|
|
string start = "start";
|
|
string finish = "end";
|
|
|
|
string lowercase = "qwertyuiopasdfghjklzxcvbnm";
|
|
|
|
int find_all_paths(unordered_map<string, set<string>> graph, vector<string> current_path, bool double_small_taken);
|
|
|
|
int main(int argc, char* argv[])
|
|
{
|
|
unordered_map<string, set<string>> graph;
|
|
|
|
string line;
|
|
while(getline(cin, line))
|
|
{
|
|
string::size_type n = line.find("-",0);
|
|
string node1 = line.substr(0,n);
|
|
string node2 = line.substr(n+1);
|
|
|
|
if (!graph.contains(node1))
|
|
{
|
|
graph.emplace(node1, set<string>());
|
|
}
|
|
|
|
if (!graph.contains(node2))
|
|
{
|
|
graph.emplace(node2, set<string>());
|
|
}
|
|
|
|
if (0 != node2.compare(start))
|
|
graph[node1].insert(node2);
|
|
if (0 != node1.compare(start))
|
|
graph[node2].insert(node1);
|
|
}
|
|
|
|
vector<string> beginning_path;
|
|
beginning_path.push_back(start);
|
|
|
|
cout << find_all_paths(graph, beginning_path, false) << endl;
|
|
}
|
|
|
|
int find_all_paths(unordered_map<string, set<string>> graph, vector<string> current_path, bool double_small_taken)
|
|
{
|
|
int found_paths = 0;
|
|
set<string> connected_nodes = graph[current_path.back()];
|
|
|
|
for (set<string>::iterator it = connected_nodes.begin(); it != connected_nodes.end(); ++it)
|
|
{
|
|
string current_node = *it;
|
|
|
|
if (current_node.compare(finish) == 0)
|
|
{
|
|
++found_paths;
|
|
}
|
|
else if (string::npos == current_node.find_first_of(lowercase) ||
|
|
current_path.end() == std::find(current_path.begin(), current_path.end(), current_node))
|
|
{ //Big cave or small cave not in path
|
|
vector<string> next_path(current_path);
|
|
next_path.push_back(current_node);
|
|
found_paths += find_all_paths(graph, next_path, double_small_taken);
|
|
}
|
|
else if (!double_small_taken)
|
|
{ //Small cave and in path, double is not taken though
|
|
vector<string> next_path(current_path);
|
|
next_path.push_back(current_node);
|
|
found_paths += find_all_paths(graph, next_path, true);
|
|
}
|
|
}
|
|
|
|
return found_paths;
|
|
} |