Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <list>
- #include <stack>
- #include <string>
- using namespace std;
- bool allArePresent(list<string> &base, list<string> &elements)
- {
- for (auto &el : elements)
- {
- bool found = false;
- for (auto &el2 : base)
- {
- if (el2 == el)
- {
- found = true;
- }
- }
- if (!found)
- {
- return false;
- }
- }
- return true;
- }
- void addIfAbsent(list<string> &l, list<string> &elements)
- {
- for (auto el : elements)
- {
- bool found = false;
- for (auto &res_el : l)
- {
- if (res_el == el)
- {
- found = true;
- break;
- }
- }
- if (!found)
- {
- l.push_back(el);
- }
- }
- }
- bool addIfAbsent(list<string> &list, string el)
- {
- bool found = false;
- for (auto &res_el : list)
- {
- if (res_el == el)
- {
- found = true;
- break;
- }
- }
- if (!found)
- {
- list.push_back(el);
- return true;
- }
- return false;
- }
- list<string> getSurroundingStations(const list<list<string>> &lines, string station)
- {
- list<string> result;
- for (const list<string> &el : lines)
- {
- string prev = "";
- auto it = el.begin();
- while (it != el.end())
- {
- if (*it == station)
- {
- if (!prev.empty())
- {
- addIfAbsent(result, prev);
- }
- it++;
- if (it != el.end())
- {
- addIfAbsent(result, *it);
- }
- break;
- }
- else
- {
- prev = *it;
- }
- it++;
- }
- }
- return result;
- }
- void printStack(stack<string> st)
- {
- while (!st.empty())
- {
- cout << st.top() << ' ';
- st.pop();
- }
- cout << '\n';
- }
- void printList(list<string> l)
- {
- for (auto &el : l)
- {
- cout << el << ' ';
- }
- cout << endl;
- }
- list<string> getPath(const list<list<string>> &lines, const string &origin, const string &destination)
- {
- list<string> visited;
- list<string> path;
- stack<string> st;
- path.push_back(origin);
- visited.push_back(origin);
- st.push(origin);
- while (!st.empty() && path.back() != destination)
- {
- cout << "List: ";
- printList(path);
- cout << "Stack: ";
- printStack(st);
- cout << endl;
- list<string> current = getSurroundingStations(lines, st.top());
- if (allArePresent(visited, current))
- {
- if (!st.empty())
- {
- st.pop();
- }
- if (!path.empty())
- {
- path.pop_back();
- }
- }
- else
- {
- if (path.back() != st.top())
- {
- path.push_back(st.top());
- }
- for (auto &el : current)
- {
- if (addIfAbsent(visited, el))
- {
- st.push(el);
- }
- if (st.top() == destination)
- {
- path.push_back(destination);
- break;
- }
- }
- if (path.back() != st.top())
- {
- path.push_back(st.top());
- }
- }
- }
- return path;
- }
- int main()
- {
- list<list<string>> lines = {{"Stranraer", "Glasgow Central", "Falkirk High", "Edinburgh"},
- {"Fort William", "Glasgow Central", "Edinburgh", "Newcastle", "York", "Doncaster", "Peterborough", "London KingsX"},
- {"Bangor", "Chester", "Crewe", "Nottingham", "Peterborough", "Norwich"},
- {"Norwich", "Cambridge", "Hitchin", "London KingsX"},
- {"Penzance", "Plymouth", "Exeter", "Swindon", "London Victoria"}};
- list<string> path = getPath(lines, "Stranraer", "Norwich");
- for (auto &el : path)
- {
- cout << el << ' ';
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement