fork(1) download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <climits>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. // individual connection data class
  9. class RoomConnection {
  10.   public:
  11.     int roomin;
  12.     int roomout;
  13.  
  14.     RoomConnection() {}
  15.     RoomConnection(int n1, int n2) {
  16.         roomin  = n1;
  17.         roomout = n2;
  18.     }
  19.  
  20.     void Print() {
  21.         cout << "[" << roomin << ", " << roomout << "]";
  22.     }
  23. };
  24.  
  25. // list of connection data class
  26. class RoomConnectionList : public vector<RoomConnection> {
  27.   public:
  28.     void push_back(RoomConnection rc) {
  29.         vector<RoomConnection>::push_back(rc);
  30.     }
  31.     void push_back(int r1, int r2) {
  32.         RoomConnection rc(r1 ,r2);
  33.         push_back(rc);
  34.     }
  35.  
  36.     void Print() {
  37.         cout << "Room Connection List : " << size() << endl;
  38.         for (vector<RoomConnection>::iterator it = begin(); it != end(); it++) {
  39.             if (it != begin()) {
  40.                 cout << " ";
  41.             }
  42.             it->Print();
  43.         }
  44.         cout << endl;
  45.     }
  46.  
  47.     // delete redundant connection
  48.     // (if connection has duplicate data, result has also duplication)
  49.     // eg. {1,2} {2,3} {1,2} {2,1} --> {1,2} {2,3}
  50.     void Unique() {
  51.         vector<RoomConnection>::iterator it, itstart, itend;
  52.         for (it = begin(); it != end(); it++) {
  53.             if (it->roomin > it->roomout) {
  54.                 std::swap(it->roomin, it->roomout);
  55.             }
  56.         }
  57.         sort(begin(), end(), SortCmp);
  58.         itstart = begin();
  59.         itend =  unique(begin(), end(), UniqueCmp);
  60.         assign(itstart, itend);
  61.     }
  62.  
  63.   private:
  64.     static bool SortCmp(RoomConnection a1, RoomConnection a2) {
  65.         if (a1.roomin > a2.roomin) {
  66.             return false;
  67.         } else if (a1.roomin == a2.roomin) {
  68.             if (a1.roomout > a2.roomout) {
  69.                 return false;
  70.             }
  71.         }
  72.         return true;
  73.     }
  74.     static bool UniqueCmp(RoomConnection a1, RoomConnection a2) {
  75.         if ((a1.roomin == a2.roomin) && (a1.roomout == a2.roomout)) {
  76.             return true;
  77.         }
  78.         return false;
  79.     }
  80. };
  81.  
  82. // individual route class
  83. class Route : public vector<int> {
  84.   public:
  85.     int Exist(int room) {
  86.         for (vector<int>::iterator it = begin(); it != end(); it++) {
  87.             if (*it == room) {
  88.                 return 1;
  89.             }
  90.         }
  91.         return 0;
  92.     }
  93.  
  94.     void Print() {
  95.         cout << "[";
  96.         for (vector<int>::iterator it = begin(); it != end(); it++) {
  97.             if (it != begin()) {
  98.                 cout << ", ";
  99.             }
  100.             cout << *it;
  101.         }
  102.         cout << "]";
  103.     }
  104. };
  105.  
  106. // list of route class
  107. class RouteList : public vector<Route> {
  108.   public:
  109.     void PrintMinimumRoute() {
  110.         if (!size()) {
  111.             cout << "No minimum route." << endl;
  112.             return;
  113.         }
  114.         int minDistance = INT_MAX;
  115.         for (vector<Route>::iterator it = begin(); it != end(); it++) {
  116.             int size = (*it).size();
  117.             minDistance = min(minDistance, size - 1);
  118.         }
  119.         cout << "Minimum Distance : " << minDistance << endl;
  120.         cout << "--------------------------------" << endl;
  121.  
  122.         int numMinRoute = 0;
  123.         for (vector<Route>::iterator it = begin(); it != end(); it++) {
  124.             int size = (*it).size();
  125.             if ((size - 1) == minDistance) {
  126.                 it->Print();
  127.                 cout << endl;
  128.                 numMinRoute++;
  129.             }
  130.         }
  131.         cout << numMinRoute << " route found." << endl;
  132.     }
  133.  
  134.     void Print() {
  135.         cout << "All route" << endl;
  136.         cout << "--------------------------------" << endl;
  137.         for (vector<Route>::iterator it = begin(); it != end(); it++) {
  138.             it->Print();
  139.             cout << endl;
  140.         }
  141.     }
  142. };
  143.  
  144. // find route with recursive
  145. void FindRoute(RoomConnectionList *conList, int roomEnd, Route *route, RouteList *routeList)
  146. {
  147.     int lastRoom = route->back();
  148.     int nextRoom;
  149.     vector<RoomConnection>::iterator it;
  150.  
  151.     for (it =  conList->begin(); it != conList->end(); it++) {
  152.         nextRoom = 0;
  153.         if (it->roomin == lastRoom) {
  154.             nextRoom = it->roomout;
  155.         } else if (it->roomout == lastRoom) {
  156.             nextRoom = it->roomin;
  157.         }
  158.  
  159.         if (nextRoom) {
  160.             if (!route->Exist(nextRoom)) { // avoid loop (back to same room?)
  161.                 Route tempRoute = *route;
  162.                 tempRoute.push_back(nextRoom);
  163.                 if (nextRoom == roomEnd) { // reach end room then add to list.
  164.                     routeList->push_back(tempRoute);
  165.                 } else {
  166.                     FindRoute(conList, roomEnd, &tempRoute, routeList);
  167.                 }
  168.             }
  169.         }
  170.     }
  171. }
  172.  
  173. // find all route (entry)
  174. void FindAllRoute(RoomConnectionList *conList, int roomStart, int roomEnd, RouteList *routeList)
  175. {
  176.     Route tempRoute;
  177.  
  178.     tempRoute.clear();
  179.     tempRoute.push_back(roomStart);
  180.     FindRoute(conList, roomEnd, &tempRoute, routeList);
  181. }
  182.  
  183. // main 
  184. int main(void)
  185. {
  186.     RoomConnectionList roomConnection;
  187.     RouteList route;
  188.  
  189.     // Room Connection List.
  190.     roomConnection.push_back(1,2);
  191.     roomConnection.push_back(1,3);
  192.     roomConnection.push_back(1,4);
  193.     roomConnection.push_back(2,5);
  194.     roomConnection.push_back(3,5);
  195.     roomConnection.push_back(4,5);
  196.     roomConnection.push_back(2,6);
  197.     roomConnection.push_back(3,6);
  198.     roomConnection.push_back(4,6);
  199.     roomConnection.push_back(5,7);
  200.     roomConnection.push_back(6,7);
  201.  
  202.     int roomStart = 1;                // start room No.
  203.     int roomEnd   = 7;                // end room No.
  204.  
  205.     roomConnection.Print();
  206.  
  207.     // check connection list (delete redundant connection)
  208.     roomConnection.Unique();
  209.  
  210.     // find all route
  211.     FindAllRoute(&roomConnection, roomStart, roomEnd, &route);
  212.  
  213.     // print result
  214.     cout << "Start Room : " << roomStart << endl;
  215.     cout << "End   Room : " << roomEnd << endl;
  216.     cout << "There are " << route.size() << " different route." << endl;
  217.     cout << endl;
  218.  
  219.     // print minimum distance
  220.     route.PrintMinimumRoute();
  221.  
  222.     // print all route (for debug)
  223.     //cout << endl << endl;
  224.     //route.Print();
  225.  
  226.     return 0;
  227. }
  228.  
  229.  
Success #stdin #stdout 0s 3284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Room Connection List : 11
[1, 2] [1, 3] [1, 4] [2, 5] [3, 5] [4, 5] [2, 6] [3, 6] [4, 6] [5, 7] [6, 7]
Start Room : 1
End   Room : 7
There are 18 different route.

Minimum Distance : 3
--------------------------------
[1, 2, 5, 7]
[1, 2, 6, 7]
[1, 3, 5, 7]
[1, 3, 6, 7]
[1, 4, 5, 7]
[1, 4, 6, 7]
6 route found.
https://ideone.com/plSjsF
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!