fork(1) download 
  1. #include <stdio.h>
  2.  
  3. #define MAX_ROUTE_LIST 2048
  4. #define MAX_ROOM       16
  5.  
  6. typedef struct Route {
  7. // room list terminate by 0.  eg. 1,2,5 -> {1,2,5,0}
  8.     int route[MAX_ROOM + 1];
  9. } Route;
  10.  
  11. int Route_Size(Route *a)
  12. {
  13.     int len = 0;
  14.  
  15.     while (a->route[len]) {
  16.         len++;
  17.     }
  18.     return len;
  19. }
  20.  
  21. int Route_PushBack(Route *a, int num)
  22. {
  23.     int len = Route_Size(a);
  24.  
  25.     if (len >= sizeof(a->route) - 1) {
  26.         return -1;
  27.     }
  28.     a->route[len] = num;
  29.     a->route[len + 1] = 0;
  30.     return 0;
  31. }
  32.  
  33. int Route_Last(Route *a)
  34. {
  35.     int i;
  36.     int last;
  37.  
  38.     i = 0;
  39.     while (a->route[i]) {
  40.         last = a->route[i];
  41.         i++;
  42.     }
  43.     return last;
  44. }
  45.  
  46. int Route_RoomExist(Route *a, int num)
  47. {
  48.     int i;
  49.  
  50.     i = 0;
  51.     while (a->route[i]) {
  52.         if (a->route[i] == num) {
  53.             return 1;
  54.         }
  55.         i++;
  56.     }
  57.     return 0;
  58. }
  59.  
  60. int RouteList_PushBack(Route *dstList, Route *src)
  61. {
  62.     int numRouteList;
  63.  
  64.     numRouteList = 0;
  65.     while ( (dstList + numRouteList)->route[0] ) {
  66.         numRouteList++;
  67.     }
  68.     if (numRouteList < MAX_ROUTE_LIST - 1) {
  69.         *(dstList + numRouteList) = *src;
  70.     } else {
  71.         printf("Route List Overflow !\n");
  72.     }
  73.     return 0;
  74. }
  75.  
  76. void PrintRoute(Route *route)
  77. {
  78.     int i;
  79.  
  80.     printf("[");
  81.     i = 0;
  82.     while ( route->route[i] ) {
  83.         if (i) {
  84.             printf(", ");
  85.         }
  86.         printf("%d", route->route[i]);
  87.         i++;
  88.     }
  89.     printf("]\n");
  90. }
  91.  
  92. void FindRoute(int roomConnectList[][2], int roomEnd, Route *route, Route *routeList)
  93. {
  94.     Route tempRoute;
  95.     int lastRoom, nextRoom;
  96.     int numConnectList;  // number of connection list
  97.     int i;
  98.  
  99.     numConnectList = 0;
  100.     while (roomConnectList[numConnectList][0] && roomConnectList[numConnectList][1]) {
  101.         numConnectList++;
  102.     }
  103.     lastRoom = Route_Last(route);
  104.  
  105.     for (i = 0; i < numConnectList; i++) {
  106.         nextRoom = 0;
  107.         if (roomConnectList[i][0] == lastRoom) {
  108.             nextRoom = roomConnectList[i][1];
  109.         } else if (roomConnectList[i][1] == lastRoom) {
  110.             nextRoom = roomConnectList[i][0];
  111.         }
  112.  
  113.         if (nextRoom) {
  114.             if (!Route_RoomExist(route, nextRoom)) {  // avoid looping (if next room is already exist in route, it will make loop)
  115.                 tempRoute = *route;
  116.                 Route_PushBack(&tempRoute, nextRoom);
  117. 	            if (nextRoom == roomEnd) {  // reach end room then add to list.
  118. 	                RouteList_PushBack(routeList, &tempRoute);
  119. 	            } else {
  120. 	                FindRoute(roomConnectList, roomEnd, &tempRoute, routeList);
  121. 	            }
  122. 	        }
  123.         }
  124.     }
  125. }
  126.  
  127. void FindAllRoute(int roomConnectList[][2], int roomStart, int roomEnd, Route *routeList)
  128. {
  129.     Route tempRoute;
  130.  
  131.     tempRoute.route[0] = roomStart;
  132.     FindRoute(roomConnectList, roomEnd, &tempRoute, routeList);
  133. }
  134.  
  135. void PrintMinimumRoute(Route *routeList)
  136. {
  137.     int minDistance = MAX_ROOM + 1;
  138.     int numRouteList, numMinRoute;
  139.     int i;
  140.  
  141.     numRouteList = 0;
  142.     while ( (routeList + numRouteList)->route[0] ) {
  143.         int n = 0;
  144.         while ( (routeList + numRouteList)->route[n++] );
  145.         if ((n - 2) < minDistance) {
  146.             minDistance = n - 2;
  147.         }
  148.         numRouteList++;
  149.     }
  150.  
  151.     printf("There are %d different route.\n", numRouteList);
  152.     printf("\n");
  153.     printf("Minimum Distance : %d\n", minDistance);
  154.     printf("--------------------------------\n");
  155.     i = 0;
  156.     numMinRoute = 0;
  157.     while ( (routeList + i)->route[0] ) {
  158.         int n = 0;
  159.         while ( (routeList + i)->route[n++] );
  160.         if ((n - 2) == minDistance) {
  161.             PrintRoute(routeList + i);
  162.             numMinRoute++;
  163.         }
  164.         i++;
  165.     }
  166.     printf("%d Route found.\n",numMinRoute);
  167.  
  168.     if (1) {  // print all route for debug
  169. 	    printf("\n\nAll Route List (for debug)\n");
  170.         printf("--------------------------------\n");
  171. 	    i = 0;
  172. 	    while ( (routeList + i)->route[0] ) {
  173. 	        int n = 0;
  174. 	        while ( (routeList + i)->route[n++] );
  175. 	        PrintRoute(routeList + i);
  176. 	        i++;
  177. 	    }
  178.     }
  179. }
  180.  
  181. void PrintRoomConnection(int roomConnectList[][2])
  182. {
  183.     int i;
  184.  
  185.     printf("Room Connection List :\n");
  186.     i = 0;
  187.     while (roomConnectList[i][0] && roomConnectList[i][1]) {
  188.         printf("{%d, %d} ", roomConnectList[i][0], roomConnectList[i][1]);
  189.         i++;
  190.     }
  191.     printf("\n");
  192. }
  193.  
  194. int main(void)
  195. {
  196.     int roomConnectList [][2] = {{1, 2}, {1, 3}, {1, 4}, {2, 5}, {3, 5},
  197.                                  {4, 5}, {2, 6}, {3, 6}, {4, 6}, {5, 7},
  198.                                  {6, 7}, {0, 0}};
  199.     int roomStart = 1;                // start room No.
  200.     int roomEnd   = 7;                // end room No.
  201.     Route routeList[MAX_ROUTE_LIST];  // buffer of result
  202.  
  203.     int i;
  204.     for (i = 0; i < MAX_ROUTE_LIST; i++) { // initialize route list
  205.         routeList[i].route[0] = 0;
  206.     }
  207.  
  208.     // find all route
  209.     FindAllRoute(roomConnectList, roomStart, roomEnd, routeList);
  210.  
  211.     // print connection and start,end room No.
  212.     PrintRoomConnection(roomConnectList);
  213.     printf("Start Room : %d\nEnd   Room : %d\n", roomStart, roomEnd);
  214.  
  215.     // print minimum distance
  216.     PrintMinimumRoute(routeList);
  217.  
  218.     return 0;
  219. }
  220.  
Success #stdin #stdout 0s 2072KB
comments (?)
stdin 
Standard input is empty
stdout 
Room Connection List :
{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.


All Route List (for debug)
--------------------------------
[1, 2, 5, 3, 6, 7]
[1, 2, 5, 4, 6, 7]
[1, 2, 5, 7]
[1, 2, 6, 3, 5, 7]
[1, 2, 6, 4, 5, 7]
[1, 2, 6, 7]
[1, 3, 5, 2, 6, 7]
[1, 3, 5, 4, 6, 7]
[1, 3, 5, 7]
[1, 3, 6, 2, 5, 7]
[1, 3, 6, 4, 5, 7]
[1, 3, 6, 7]
[1, 4, 5, 2, 6, 7]
[1, 4, 5, 3, 6, 7]
[1, 4, 5, 7]
[1, 4, 6, 2, 5, 7]
[1, 4, 6, 3, 5, 7]
[1, 4, 6, 7]
https://ideone.com/rFYGRr
language:
C (gcc 8.3)
created:
11 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!