#include <stdio.h> #define MAX_ROUTE_LIST 2048 #define MAX_ROOM 16 typedef struct Route { // room list terminate by 0. eg. 1,2,5 -> {1,2,5,0} int route[MAX_ROOM + 1]; } Route; int Route_Size(Route *a) { int len = 0; while (a->route[len]) { len++; } return len; } int Route_PushBack(Route *a, int num) { int len = Route_Size(a); if (len >= sizeof(a->route) - 1) { return -1; } a->route[len] = num; a->route[len + 1] = 0; return 0; } int Route_Last(Route *a) { int i; int last; i = 0; while (a->route[i]) { last = a->route[i]; i++; } return last; } int Route_RoomExist(Route *a, int num) { int i; i = 0; while (a->route[i]) { if (a->route[i] == num) { return 1; } i++; } return 0; } int RouteList_PushBack(Route *dstList, Route *src) { int numRouteList; numRouteList = 0; while ( (dstList + numRouteList)->route[0] ) { numRouteList++; } if (numRouteList < MAX_ROUTE_LIST - 1) { *(dstList + numRouteList) = *src; } else { } return 0; } void PrintRoute(Route *route) { int i; i = 0; while ( route->route[i] ) { if (i) { } i++; } } void FindRoute(int roomConnectList[][2], int roomEnd, Route *route, Route *routeList) { Route tempRoute; int lastRoom, nextRoom; int numConnectList; // number of connection list int i; numConnectList = 0; while (roomConnectList[numConnectList][0] && roomConnectList[numConnectList][1]) { numConnectList++; } lastRoom = Route_Last(route); for (i = 0; i < numConnectList; i++) { nextRoom = 0; if (roomConnectList[i][0] == lastRoom) { nextRoom = roomConnectList[i][1]; } else if (roomConnectList[i][1] == lastRoom) { nextRoom = roomConnectList[i][0]; } if (nextRoom) { if (!Route_RoomExist(route, nextRoom)) { // avoid looping (if next room is already exist in route, it will make loop) tempRoute = *route; Route_PushBack(&tempRoute, nextRoom); if (nextRoom == roomEnd) { // reach end room then add to list. RouteList_PushBack(routeList, &tempRoute); } else { FindRoute(roomConnectList, roomEnd, &tempRoute, routeList); } } } } } void FindAllRoute(int roomConnectList[][2], int roomStart, int roomEnd, Route *routeList) { Route tempRoute; tempRoute.route[0] = roomStart; FindRoute(roomConnectList, roomEnd, &tempRoute, routeList); } void PrintMinimumRoute(Route *routeList) { int minDistance = MAX_ROOM + 1; int numRouteList, numMinRoute; int i; numRouteList = 0; while ( (routeList + numRouteList)->route[0] ) { int n = 0; while ( (routeList + numRouteList)->route[n++] ); if ((n - 2) < minDistance) { minDistance = n - 2; } numRouteList++; } i = 0; numMinRoute = 0; while ( (routeList + i)->route[0] ) { int n = 0; while ( (routeList + i)->route[n++] ); if ((n - 2) == minDistance) { PrintRoute(routeList + i); numMinRoute++; } i++; } if (1) { // print all route for debug i = 0; while ( (routeList + i)->route[0] ) { int n = 0; while ( (routeList + i)->route[n++] ); PrintRoute(routeList + i); i++; } } } void PrintRoomConnection(int roomConnectList[][2]) { int i; i = 0; while (roomConnectList[i][0] && roomConnectList[i][1]) { i++; } } int main(void) { int roomConnectList [][2] = {{1, 2}, {1, 3}, {1, 4}, {2, 5}, {3, 5}, {4, 5}, {2, 6}, {3, 6}, {4, 6}, {5, 7}, {6, 7}, {0, 0}}; int roomStart = 1; // start room No. int roomEnd = 7; // end room No. Route routeList[MAX_ROUTE_LIST]; // buffer of result int i; for (i = 0; i < MAX_ROUTE_LIST; i++) { // initialize route list routeList[i].route[0] = 0; } // find all route FindAllRoute(roomConnectList, roomStart, roomEnd, routeList); // print connection and start,end room No. PrintRoomConnection(roomConnectList); // print minimum distance PrintMinimumRoute(routeList); return 0; }
Standard input is empty
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]