OJ Board

Code: Select all

CASE 1:
1 2 3 4 6
1 2 3 5 6
1 2 4 3 5 6
1 2 4 6
1 3 2 4 6
1 3 4 6
1 3 5 6
There are 7 routes from the firestation to streetcorner 6.
CASE 2:
1 3 2 5 7 8 9 6 4
1 3 4
1 5 2 3 4
1 5 7 8 9 6 4
1 6 4
1 6 9 8 7 5 2 3 4
1 8 7 5 2 3 4
1 8 9 6 4
There are 8 routes from the firestation to streetcorner 4.

Code: Select all

//208 Firetruck
//https://uva.onlinejudge.org/external/2/208.pdf

#define _CRT_SECURE_NO_WARNINGS

#include<stdio.h>

#define MAX 22
#define MAXNODE 100
#define INFINITY 32767

int addj[MAXNODE][MAXNODE];
int visited[MAXNODE][MAXNODE];
int path[1000];
int trout = 0;
int vist[MAXNODE];
int dist[MAXNODE][MAXNODE];
void init()
{
	for (int i = 0; i <= MAXNODE; i++)
	{
		path[i] = 0;
		vist[i] = 0;
		for (int j = 0; j <= MAXNODE; j++)
		{
			addj[i][j] = visited[i][j] = 0;
			dist[i][j] = INFINITY;
		}

	}
}

void foloyd_warshal(int maxnode)
{
	for (int i = 0; i <= maxnode; i++)
	{
		dist[i][i] = 0;
	}

	for (int k = 0; k <= maxnode; k++)
	{
		for (int i = 0; i <= maxnode; i++)
		{
			for (int j = 0; j <= maxnode; j++)
			{
				if (dist[i][j] > dist[i][k] + dist[k][j])
				{
					dist[i][j] = dist[i][k] + dist[k][j];
				}
			}

		}
	}
}




void find_rout(int node,int firecorner,int maxnode,int index)
{
	int np = 0;
	if (node == firecorner)
	{
		//printf("   ");
		int i = 0;
		for (i = 0; i < index-1; i++)
			printf("%d ",path[i]);
		printf("%d", path[i]);
		printf("\n");
		trout++;
		return ;
	}
	for (int v = 0; v <= maxnode; v++)
	{
		if (((addj[node][v]) && (!vist[v])) && (dist[firecorner][v]<INFINITY))
		{
			visited[node][v] = 1;
			path[index] = v;
			np = v;
			vist[v] = 1;
			find_rout(np, firecorner, maxnode, index + 1);
			vist[np] = 0;
			/*if (np>2)
				vist[np] = 0;*/
		}
	}
}

int main()
{
	int firecorner = 0,case1=1;
	int u, v,maxnode;
	/*freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);*/

	while (scanf("%d", &firecorner) != EOF)
	{
		maxnode = 0;
		trout = 0;
		init();
		while (1)
		{
			scanf("%d %d", &u, &v);
			if (u == 0 && v == 0)
				break;
			addj[u][v] = 1;
			addj[v][u] = 1;
			dist[u][v] = 1;
			dist[v][u] = 1;
			if (maxnode < u)
				maxnode = u;
			if (maxnode < v)
				maxnode = v;
		}
		foloyd_warshal(maxnode);
		path[0] = 1;
		vist[1] = 1;
		printf("CASE %d:\n", case1++);
		find_rout(1, firecorner,maxnode,1);
		printf("There are %d routes from the firestation to streetcorner %d.\n", trout,firecorner);
	}

	return 0;
}