#include <stdio.h>
#include <conio.h>

void add_pointers(char parent,char child,char pointers[][2])
{
    int cnt=0;
	while(pointers[cnt++][0]!=-1);
	pointers[cnt-1][0] = parent;
	pointers[cnt-1][1] = child;
	pointers[cnt][0] = pointers[cnt][1] = -1;
}
void print_route(char pointers[][2])
{
	char tofind = 'G';

	char route[1024];
	route[0] = tofind;
	int n_route = 1;

	while(tofind != 'S'){
		for(int cnt=0;pointers[cnt][0]!=0;cnt++){
			if(pointers[cnt][1] == tofind){
				route[n_route] = pointers[cnt][0];
				n_route++;
				tofind = pointers[cnt][0];
				break;
			}
		}
	}

	for(int cnt=n_route-1;cnt>=0;cnt--){
		printf("%c",route[cnt]);
		if(cnt!=0){
			printf(" -> ");
		}
	}
	printf("\n");
}
int has_node(char buf[][2],char node[2])
{
	for(int cnt=0;buf[cnt][0]!=-1;cnt++){
		if(buf[cnt][0] == node[0]){
			return buf[cnt][1];
		}
	}
	return -1;
}
bool add_node(char buf[][2],char node[2])
{
	if(node[0] == 'G'){
		char bk[2] = {buf[0][0],buf[0][1]};
		int cnt=1;
		while(bk[0]!=-1){
			char bk2[2] = {buf[cnt][0],buf[cnt][1]};
			buf[cnt][0] = bk[0];
			buf[cnt][1] = bk[1];
			bk[0] = bk2[0];
			bk[1] = bk2[1];
			cnt++;
		}
		buf[cnt][0] = -1;
		buf[0][0] = node[0];
		buf[0][1] = node[1];
	}else{
		int cnt=0;
		while(buf[cnt++][0]!=-1);
		buf[cnt-1][0] = node[0];
		buf[cnt-1][1] = node[1];
		buf[cnt][0] = -1;
	}
	return true;
}
bool remove_node(char buf[][2],char node[2])
{
	for(int cnt=0;buf[cnt][0]!=-1;cnt++){
		if(buf[cnt][0]==node[0]){
			int cnt2=cnt+1;
			for(;buf[cnt2][0]!=-1;cnt2++){
				buf[cnt2-1][0] = buf[cnt2][0];
				buf[cnt2-1][1] = buf[cnt2][1];
			}
			buf[cnt2-1][0] = -1;
			return true;
		}
	}
	return true;
}
int print_list(char list[][2])
{
	int printed = 0;
	for(int cnt=0;list[cnt][0]!=-1;cnt++){
		if(cnt!=0){
			printf(",");
		}
		printf("%c(%d)",list[cnt][0],list[cnt][1]);
		printed++;
	}
	return printed;
}
int main()
{
	char graph[][3] = {
		{'S','B',0},
		{'S','C',0},
		{'S','D',0},
		{'B','A',0},
		{'A','C',0},
		{'C','D',0},
		{'D','G',0},
		{-1,-1,-1},
	};

	char open[2048][2] = {{'S',0},{-1,-1}};
	char closed[2048][2] = {{-1,-1}};
	char pointers[2048][2] = {{-1,-1}};

	printf("OPEN\t\tCLOSED\n");
	while(open[0][0] != -1){
		
		int printed = print_list(open);
		printf(printed>=2?"\t":"\t\t");
		print_list(closed);
		printf("\n");
		
		char n[2] = {open[0][0],open[0][1]};
		if(n[0] == 'G'){
			print_route(pointers);
			return 1;
		}else{
			remove_node(open,n);
			add_node(closed,n);

			for(int cnt=0;graph[cnt][0]!=0;cnt++){
				if(graph[cnt][0] == n[0]){
					char m[2] = {graph[cnt][1],n[1]+graph[cnt][2]};

					if(has_node(open,m)==-1 && has_node(closed,m)==-1){
						add_pointers(n[0],m[0],pointers);
						add_node(open,m);
					}
				}
			}
		}
	}
	printf("ルートを発見できませんでした。\n");

	return 0;
}