/** * Find the shortest city-to-city distance in number of moves. We take in the * endpoints of the search and return the closest city by reference. We also * return the number of steps to that point. * * This would be much better if we could use a map! */#define DEBUG_RECURSIVE 0int city_distance(City *from, City *to, City **closest, std::vector<std::pair<City *, unsigned int> >& history, unsigned int depth) {#if DEBUG_RECURSIVE std::cout << "\tSubcalculation from " << from->name() << " to " << to->name() << std::endl;#endif // Don't bother going further if we've found an easier solution static unsigned int foundDepth = 0; if(depth == 0) { foundDepth = 0; } else if(foundDepth > 0 && depth > foundDepth) {#if DEBUG_RECURSIVE std::cout << "\t\tThis is deeper than we found our last solution, giving up." << std::endl;#endif return -1; } // Look us up in the history; have we been here before? std::vector<std::pair<City *, unsigned int> >::iterator histit; for(histit = history.begin(); histit != history.end(); histit ++) { if(histit->first == from) { // If we've been here before in fewer steps, send the kill signal if(histit->second <= depth) {#if DEBUG_RECURSIVE std::cout << "\t\tI previously made it here in " << (depth - histit->second) << " fewer moves." << std::endl;#endif return -1; // Otherwise, update the depth to our new, lower number } else {#if DEBUG_RECURSIVE std::cout << "\t\tThis path is " << (histit->second - depth) << " moves shorter than the last one." << std::endl;#endif histit->second = depth; break; } } } // It's entirely possible this wasn't in the history at all, so we need to // add it, of course. if(histit == history.end()) {#if DEBUG_RECURSIVE std::cout << "\t\tI have never been in " << from->name() << " before." << std::endl;#endif history.push_back(std::make_pair(from, depth)); } // If we've reached our destination, return the depth if(from == to) {#if DEBUG_RECURSIVE std::cout << "\t\tThis is my destination." << std::endl;#endif foundDepth = depth; return depth; } /** * Now we have the task of looping through the neighbors and making the * recursive call on them, then tallying up the number of moves and figuring * out which one is the shortest. Oh joy! */ // The first step is to see if we're neighboring the target as-is. if(from->is_neighbor(to)) {#if DEBUG_RECURSIVE std::cout << "\t\tI am neighboring my destination." << std::endl;#endif return city_distance(to, to, closest, history, depth + 1); } // If not, we recurse with each neighbor and store the minimum distance#if DEBUG_RECURSIVE std::cout << "\t\tFinding shortest distance path recursively" << std::endl;#endif unsigned int min = 0; for(std::vector<City *>::const_iterator it = from->get_neighbors().begin(); it != from->get_neighbors().end(); it ++) { if(*it == NULL) { continue; } // Propagate the search down once more int dist = city_distance(*it, to, closest, history, depth + 1); // If we received a -1, it means this path is hopeless if(dist == -1) {#if DEBUG_RECURSIVE std::cout << "\t\tThe path from " << (*it)->name() << " to " << to->name() << " was a dead-end." << std::endl;#endif continue; } // If this is shorter than we had previously, store it if(min == 0 || (unsigned int)dist < min) {#if DEBUG_RECURSIVE std::cout << "\t\tThe path from " << (*it)->name() << " to " << to->name() << " is shorter than my previous best: " << dist << std::endl;#endif if(depth == 0) { *closest = *it;#if DEBUG_RECURSIVE std::cout << "\t\tThis is the closest neighbor to our starting point." << std::endl;#endif } min = dist; } // We can't have a path shorter than 2 moves, so might as well bail out if(min == 2) { return 2; } } // We can never have a 0-move solution, so this means that it was a dead-end if(min == 0) { return -1; } else { return min; }}/** * Driver function for recursive algorithm. See above. */unsigned int city_distance(City *from, City *to, City **closest) { // We must have both parameters non-null assert(from != NULL && to != NULL);#if DEBUG_RECURSIVE std::cout << "Beginning distance calculation from " << from->name() << " to " << to->name() << std::endl;#endif // The distance between a city and itself is zero if(from == to) { *closest = to;#if DEBUG_RECURSIVE std::cout << "No need to move anywhere!" << std::endl << std::endl;#endif return 0; } // The distance between a city and its neighbor is one if(from->is_neighbor(to)) {#if DEBUG_RECURSIVE std::cout << from->name() << " neighbors " << to->name() << std::endl << std::endl;#endif *closest = to; return 1; } // Make a history vector std::vector<std::pair<City *, unsigned int> > history; // Recursively search the tree *closest = NULL; int dist = city_distance(from, to, closest, history, 0);#if DEBUG_RECURSIVE std::cout << "Calculation finished. Shortest path is " << dist << " moves." << std::endl << std::endl;#endif return (unsigned int)dist;}