diff options
1 files changed, 0 insertions, 83 deletions
| -rw-r--r-- | Year 2/Structures and data algorithms/Project/exb/City.cpp | 83 |
diff --git a/Year 2/Structures and data algorithms/Project/exb/City.cpp b/Year 2/Structures and data algorithms/Project/exb/City.cpp deleted file mode 100644 index 1fb04ca..0000000 --- a/Year 2/Structures and data algorithms/Project/exb/City.cpp +++ /dev/null @@ -1,83 +0,0 @@ -#include "CityVisit.h" - -CityVisit::Landmark* CityVisit::find(const std::string& name) { - for (Landmark* l : landmarks) { - if (l->name == name) - return l; - } - return nullptr; -} - -void CityVisit::pushLandmarks(const std::string& from, const std::string& to, unsigned time) { - Landmark* a = find(from); - if (a == nullptr) { - a = new Landmark(from); - landmarks.push_back(a); - } - Landmark* b = find(to); - if (b == nullptr) { - b = new Landmark(to); - landmarks.push_back(b); - } - - a->visitable.push_back({ b, time }); - b->visitable.push_back({ a, time }); -} - -void CityVisit::parse(std::ifstream& inFile) { - unsigned k = 0, r = 0; - inFile >> k >> r; - - std::string name1; - std::string name2; - unsigned time = 0; - while (r-- > 0) { - inFile >> name1 >> name2 >> time; - pushLandmarks(name1, name2, time); - } - inFile >> availableTime; -} - -void CityVisit::visitTheMostInTimeRec(Landmark* currentLandmark, std::deque<Landmark*> currPath, std::deque<Landmark*> unique, int timeLeft, std::deque<Landmark*>& bestPath, unsigned& uniqueCount) { - if (timeLeft < 0) return; - - bool currentExists = false; - for (const Landmark* l : unique) { - if (l == currentLandmark) { - currentExists = true; - break; - } - } - if (!currentExists) - unique.push_back(currentLandmark); - - currPath.push_back(currentLandmark); - - if (currentLandmark->name == "Railstation" && unique.size() > uniqueCount) { - bestPath = currPath; - uniqueCount = unique.size(); - } - - for (auto lp : currentLandmark->visitable) { - visitTheMostInTimeRec(lp.first, currPath, unique, timeLeft - lp.second, bestPath, uniqueCount); - } -} - -std::deque<std::string> CityVisit::visitTheMostInTime(std::ifstream& inFile) { - landmarks.clear(); - parse(inFile); - - Landmark* station = find("Railstation"); - if (station == nullptr) - throw std::logic_error("No landmark named Railstation exists!"); - - std::deque<Landmark*> outLandmarks; - unsigned uniqueCount = 0; - visitTheMostInTimeRec(station, std::deque<Landmark*>(), std::deque<Landmark*>(), availableTime, outLandmarks, uniqueCount); - - std::deque<std::string> out; - for (Landmark* l : outLandmarks) { - out.push_back(l->name); - } - return out; -} |
