#include #include #include #include #include #include "mapstuff.h" using namespace std; /* class hashtable has hashtable(int initial_capacity); void add(const keyT &, const valT &); valT find(const keyT &) const; class set has set(int initial_capacity); void add(const keyT &); bool contains(const keyT &) const; void remove(const keyT &); class place has place(const string & name); void add_exit(road *); string get_name() const; int num_exits() const; road * get_exit(int) const; class road has road(const string & name, int length, place *, place *); string get_name() const; int get_length() const; place * get_other_end(const place *) const; ordinary function void readmap(hashtable & HT, const string & fname); */ place * ask_for_place(const string & which, hashtable & HT) { while (true) { string s; cout << "Enter " << which << ": "; cin >> s; if (cin.fail()) { cout << "\n"; exit(0); } place * p = HT.find(s); if (p == NULL) { cout << "not found\n"; continue; } return p; } } void explore_path(place * here, place * target, set & closed, vector & placepath, vector & bestplacepath, vector & roadpath, vector & bestroadpath, int & bestsofar, int travelled, int depth = 0) // total distance or negative for failure { if (here == target) { cout << "found solution, " << travelled << " miles\n"; if (travelled < bestsofar) { bestsofar = travelled; bestplacepath = placepath; bestroadpath = roadpath; } return; } int n = here->num_exits(); if (n == 0) return; if (closed.contains(here)) return; closed.add(here); for (int i = 0; i < n; i += 1) { road * r = here->get_exit(i); place * there = r->get_other_end(here); int length = r->get_length(); cout << setw(3 * depth) << "" << "Trying " << r->get_name() << " from " << here->get_name() << " to " << there->get_name()<< ", " << length << " more miles\n"; roadpath.push_back(r); placepath.push_back(here); explore_path(there, target, closed, placepath, bestplacepath, roadpath, bestroadpath, bestsofar, travelled + length, depth + 1); placepath.pop_back(); roadpath.pop_back(); cout << setw(3 * depth) << "" << "backtracked to " << here->get_name() << "\n"; } cout << setw(3 * depth) << "" << "no more exits to try from " << here->get_name() << "\n"; closed.remove(here); } int main(int argc, char * argv[]) { hashtable HT; readmap(HT, "nebraska.txt"); place * start, * target; if (argc != 3) { start = ask_for_place("starting place", HT); target = ask_for_place("destination", HT); } else { start = HT.find(argv[1]); if (start == NULL) { cerr << argv[1] << " not found\n"; exit(1); } target = HT.find(argv[2]); if (target == NULL) { cerr << argv[2] << " not found\n"; exit(1); } } vector placepath, bestplacepath; vector roadpath, bestroadpath; set closed; int dist = 0x7FFFFFFF; placepath.push_back(start); explore_path(start, target, closed, placepath, bestplacepath, roadpath, bestroadpath, dist, 0, 0); if (dist == 0x7FFFFFFF) cout << "no path found\n"; else { cout << "path of length " << dist << " miles found\n"; for (int i = 0; i < bestroadpath.size(); i += 1) { place * from = bestplacepath[i], * to = bestplacepath[i + 1]; road * rd = bestroadpath[i]; cout << "from " << from->get_name() << " " << rd->get_name() << " " << rd->get_length() << " miles to " << to->get_name() << "\n"; } } }