#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 {
        printf("Route List Overflow !\n");
    }
    return 0;
}

void PrintRoute(Route *route)
{
    int i;
    
    printf("[");
    i = 0;
    while ( route->route[i] ) {
        if (i) {
            printf(", ");
        }
        printf("%d", route->route[i]);
        i++;
    }
    printf("]\n");
}

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++;
    }
    
    printf("There are %d different route.\n", numRouteList);
    printf("\n");
    printf("Minimum Distance : %d\n", minDistance);
    printf("--------------------------------\n");
    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++;
    }
    printf("%d Route found.\n",numMinRoute);
    
    if (1) {  // print all route for debug
	    printf("\n\nAll Route List (for debug)\n");
        printf("--------------------------------\n");
	    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;
    
    printf("Room Connection List :\n");
    i = 0;
    while (roomConnectList[i][0] && roomConnectList[i][1]) {
        printf("{%d, %d} ", roomConnectList[i][0], roomConnectList[i][1]);
        i++;
    }
    printf("\n");
}

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);
    printf("Start Room : %d\nEnd   Room : %d\n", roomStart, roomEnd);
    
    // print minimum distance
    PrintMinimumRoute(routeList);
    
    return 0;
}