//En este programa se implementa, en un vector de registros, la abstracción
//de un grafo. Se realizan los recorridos en anchura y  profundidad, más
//algunas heurísticas
//Humberto Mazuera Párraga. 1998
																															 //Vuelos.CPP
#include <IOStream.H>
#include <IOManip.H>
#include <FStream.H>
#include <ConIO.H>
#include <ConStream.H>
#include <CType.H>
#include <StdLib.H>
#include <StdIO.H>
#include <Process.H>
#include <DOS.H>
#include <Graphics.H>
/*==========================================================================*/
/*A CONTINUACION DEFINICION DE PROTOTIPOS DE TODAS LAS FUNCIONES UTILIZADAS */
/*==========================================================================*/
void CapturarVuelo();
void ListarVector();
void OrdenarVuelosDesde();
void EncontrarRegistro();
void EliminarRegistro();
void ModificarRegistro();
void LeerArchivoYCargarEnVector();
void GrabarVectorEnArchivo();
void ImprimirEnPapelRegistros();
void Graficarbarras();
//----------------------------------------------------------------------------
void MeterEnPila(char *Desde, char *Hacia, int Distancia);
void SacarDePila(char *Desde, char *Hacia, int *Distancia);
void BorrarMarcas();
void Ruta(char *Hacia);
int VueloDirecto(char *Desde, char *Hacia);
int EncuentraEscala(char *Desde, char *OtraCiudad);
int RecorridoEnProfundidad(char *Desde, char *Hacia);
int RecorridoEnAnchura(char *Desde, char *Hacia);
void Recorridos();
void EliminacionDeNodos();
void EliminacionDeCaminos();
void SolucionOptima();
//----------------------------------------------------------------------------
int IniciaMouse( int &BotonMouse);
void MuestraMouse( void );
void EscondeCursorMouse( void );
int LeerTeclaXYMouse( int &x, int &y);
//----------------------------------------------------------------------------
void MueveHori(int Fondo, int Color, int x, char *p, char *Comentario);
int SubMenu1(int X, int Y);
int SubMenu2(int X, int Y);
int SubMenuListados(int X, int Y);
int SubMenuMultiples(int X, int Y);
void Ayuda(char *Cad);
void LineaFinal(char *Cad);
void Marco(int Xo,int Yo, int Xf, int Yf, int Color);
//----------------------------------------------------------------------------
int CompararCadenas(char *cadena1, char *cadena2);
void AsignarCadena(char *cadena2, char *cadena1);
int LongitudCadena(char *cadena);
char AMayuscula(char c);
void EliminarEspaciosAlInicio(char *c);
void Apropiado(char *c);
/*==========================================================================*/

/*==========================================================================*/
//Constantes necesarias para el dise¤o de los men£
const int C1=WHITE;
const int C2=BLACK;
const int C3=GREEN;
const int C4=RED;
const int Abj=80;
const int Arr=72;
const int Der=77;
const int Izq=75;
const int F1=59;
const int AltX=45;
const int Entrar=13;
const int Esc=27;

/*==========================================================================*/
//Variables globales, de tipo class constream, que definen ventanas
constream Ventanita, Menu, Escritorio, Escribir;

/*==========================================================================*/
/*A CONTINUACION CONSTANTES, VARIABLES Y FUNCIONES NECESARIAS PARA          */
/*MANTENIMIENTO DE BASE DE CONOCIMIENTO DE RUTAS DE VUELOS                  */
/*==========================================================================*/
const int MaxVuelos=100;
char NombreArchivo[]={"Conocimi.ent"};

typedef struct VUELO VUELO;

struct VUELO{
	char Desde[20];
	char Hacia[20];
	int Distancia;
	char Visitado; // utilizado en el retroseguimiento
} Vuelo[MaxVuelos]  ;  // vector de registros de todos los vuelos

int NumVuelos=0; //Contador para el n£mero de registros,(N£mero de vuelos)

//A CONTINUACION FUNCIONES NECESARIAS PARA EFECTUAR CAPTURA DE REGISTRO
VUELO LeerTeclas(int xi, int yi, int xf, int yf,
			int fondo, int color )
{
	int x=1, y=1, mx=xf-xi+1, my=yf-yi+1, terminar=0, tab=5;
	char pantalla[25][80], c;
	VUELO Registro;

	for(int i= 0; i<25; i++)
		for(int j= 0; j<80; j++)
			pantalla[i][j] = NULL;

	textbackground(fondo);	textcolor(color);
	window(xi,yi,xf,yf); clrscr();
	do{
		c = getch();
		switch (c) {
			case  0: c = getch();  //teclas de funci¢n
						switch(c){
							case 45: terminar = 1; break;      //Alt+W
							case 71: gotoxy(x=1,y=1); break;   //HOME
							case 79: gotoxy(x=mx,y=my); break; //END
							case 73: gotoxy(x,y=1); break; //page up
							case 81: gotoxy(x,y=my); break; //page down
							case 72: --y;           //Arriba
											 if (y<1) y=my;
											 gotoxy(x, y);
											 break;
							case 80: ++y;          //Abajo
											 if (y>my)  y=1;
											 gotoxy(x, y);
											 break;
							case 75: --x;           //Izquierda
											 if (x<1) x=mx;
											 gotoxy(x, y);
											 break;
							case 77: ++x;            //Derecha
											 if (x>mx) x=1;
											 gotoxy(x, y);
											 break;
							case 82: ; break;       //tecla de INSert
							case 83: ; putchar(32); //tecla de DELete
											gotoxy(x,y);
											pantalla[y-1][x-1] = (char)32;
											break;
						}
						break;
			case  3: 	terminar = 1; break;   //Ctrl-C
			case  8:	--x;                   //Tecla Retroceso
								if (x<1) x=1;
								else{
									gotoxy(x,y); putchar(32);
									pantalla[y-1][x-1]=(char)32;
								}
								gotoxy(x, y); break;//escribe blanco y retrocede
			case  9:	x+=tab;               //Tecla tabulador
								if (x>mx) x=mx;
								gotoxy(x, y); break;
			case 13: 	x=1; y++;			 //Enter
								if (y>my) terminar=1;
								gotoxy(x, y); break;
			case 27: 	terminar = 1;     // tecla de escape
			default: 	putchar(c);
								pantalla[y-1][x-1]=c;
								++x;
								if (x>mx) x=mx;
								gotoxy(x, y);
		}
	} while(!terminar);

	char *p;

	p = pantalla[0];	EliminarEspaciosAlInicio(p);	Apropiado(p);
	AsignarCadena(Registro.Desde, p);

	p = pantalla[1];	EliminarEspaciosAlInicio(p);	Apropiado(p);
	AsignarCadena(Registro.Hacia, p);

	p = pantalla[2];	EliminarEspaciosAlInicio(p);
	Registro.Distancia =  atoi(p);

	Registro.Visitado='0';

	return Registro;
}

void CapturarVuelo(){

	Marco(1,2, 40, 8, WHITE);
	Escribir.window(3,3,38,7);
	textbackground(BLUE);	textcolor(WHITE);	Escribir.clrscr();

	if(NumVuelos < MaxVuelos){
		Escribir <<"Digite ciudades y distancia ruta\n\n";
		Escribir <<"Desde     :       \n";
		Escribir <<"Hacia     :       \n";
		Escribir <<"Distancia :       \n";

		Vuelo[NumVuelos]=LeerTeclas(15,4,35,6, LIGHTGRAY, DARKGRAY);
		NumVuelos++;
	}
	else
		Escribir << "Vector de registros est  lleno\a\a";
}

void ListarVector(){

	Escritorio.window(1,2,80,24);
	textbackground(CYAN);	textcolor(YELLOW);	Escritorio.clrscr();
	if(NumVuelos){
		Escritorio <<"Registro  Desde             Hacia               Distancia\n";
		for(int i=0; i < NumVuelos; i++)
			Escritorio << setiosflags(ios::right) << setw(4) << i << "      "
					 << setiosflags(ios::left) << setw(20) << Vuelo[i].Desde
					 << setiosflags(ios::left) << setw(20) << Vuelo[i].Hacia
					 << setiosflags(ios::right) << setw(15) << Vuelo[i].Distancia
					 << endl;
	}
	else
		cout << "No hay registros en la base de conocimientos\a\a";
	getch();
}

void OrdenarVuelosDesde(){
	register int i, j;
	VUELO aux;

	if(NumVuelos){
		for (i = 0; i < NumVuelos-1; i++)
			for (j = i+1; j < NumVuelos; j++)
				if (CompararCadenas(Vuelo[i].Desde,Vuelo[j].Desde)>0){
					aux = Vuelo[i];
					Vuelo[i] = Vuelo[j];
					Vuelo[j] = aux;
				}
		ListarVector();
	}
	else
		Escritorio << "No hay registros en memoria \a\a";
}

void EncontrarRegistro() {
	char Clave[25]="";
	int	i=0, Encontrado=0;

	Escritorio.clrscr();
	if(!NumVuelos){
		Escritorio << "No hay registros de vuelos en memoria";
	}
	else{
		Escritorio <<"\nDigite Nombre ciudad de origen(Desde) y mostrar sus vuelos: ";
		gets(Clave);	Apropiado(Clave);
		while( i<NumVuelos ){
			if( CompararCadenas(Clave,Vuelo[i].Desde)==0){//Cadenas iguales
				if(!Encontrado)
					Escritorio <<"Registro  Desde             Hacia                Distancia\n";
				Escritorio << setiosflags(ios::right) << setw(4) << i << "   "
						 << setiosflags(ios::left) << setw(20) << Vuelo[i].Desde
						 << setiosflags(ios::left) << setw(20) << Vuelo[i].Hacia
						 << setiosflags(ios::right) << setw(15) << Vuelo[i].Distancia
						 << endl;
				Encontrado++;
			}
			i++;
		}
		if(Encontrado)
			Escritorio << "Desde esta ciudad hay " << Encontrado << " vuelos ";
		else
			Escritorio << "Desde esta ciudad NO hay ning£n vuelo\a";
	}

	getch();
}

void EliminarRegistro(){
	char ClaveDesde[25]="", ClaveHacia[25]="";
	int i, pos;

	Escritorio.clrscr();
	if(NumVuelos){
		Escritorio <<"\nPara ruta a borrar digite ciudad (Desde) de origen: ";
		gets(ClaveDesde);	Apropiado(ClaveDesde);
		Escritorio <<"\nPara ruta a borrar digite ciudad (Hacia) de destino: ";
		gets(ClaveHacia);	Apropiado(ClaveHacia);
		pos = 0;
		while(pos<NumVuelos && !(CompararCadenas(Vuelo[pos].Desde,ClaveDesde)==0
					&&
					CompararCadenas(Vuelo[pos].Hacia,ClaveHacia)==0)
				 )
			pos++;

		if (pos==NumVuelos){
			Escritorio <<"Ruta no encontrada, entre " <<ClaveDesde <<" y " <<ClaveHacia;
			delay(1000);
		}
		else {  //Se encontr¢ la ruta en la posici¢n pos, se procede a borrar:
			for(   ; pos<NumVuelos-1; pos++)
				Vuelo[pos] = Vuelo[pos+1];
			NumVuelos--;
		}
	}
	else
		Escritorio << "No hay registros en memoria";
}

void ModificarRegistro(){
	int registro;;

	Escritorio.clrscr();
	if (!NumVuelos){
		Escritorio <<"\n\nNo existen registros en memoria \a"; delay(1000);
	}
	else {
		Escritorio <<"\nDigite n£mero de registro a modificar: ";
		cin >> registro;
		if( registro >= 0 && registro < NumVuelos) {
			Escritorio <<"\nDigite nueva informaci¢n para Registro: " << registro;
			Escritorio <<"\nDesde: ";
			gets(Vuelo[registro].Desde);	Apropiado(Vuelo[registro].Desde);
			Escritorio <<"\nHacia: ";
			gets(Vuelo[registro].Hacia);	Apropiado(Vuelo[registro].Hacia);
			Escritorio <<"Distancia: ";    cin >> Vuelo[registro].Distancia;
		}
	}
}

void LeerArchivoYCargarEnVector(){
	fstream Archivo;

	Escritorio.clrscr();
	Archivo.open(NombreArchivo,ios::in|ios::binary);
	if(Archivo){
		NumVuelos=0;
		while( Archivo.read( (char *)&Vuelo[NumVuelos], sizeof(Vuelo[NumVuelos]) ) ){
				EliminarEspaciosAlInicio(Vuelo[NumVuelos].Desde);
				Apropiado(Vuelo[NumVuelos].Desde);
				EliminarEspaciosAlInicio(Vuelo[NumVuelos].Hacia);
				Apropiado(Vuelo[NumVuelos].Hacia);
				NumVuelos++;
		}
		Archivo.close();
	} else
		Escritorio << "No se pudo abrir el archivo";
}

void GrabarVectorEnArchivo(){
	fstream Archivo;

	Archivo.open(NombreArchivo, ios::out|ios::binary|ios::trunc);
	if (!Archivo)
		Escritorio << "Error en la apertura del archivo \a";
	else{
		for(int i=0; i<NumVuelos; i++)
			Archivo.write((char *)&Vuelo[i], sizeof(Vuelo[i]));
		Archivo.close();
	}
}
/*============================================================================
	A continuaci¢n algunas macros que le serviran para cambiar el tipo de
	letra en impresora Epson de matriz de punto.
 Consulte el manual de su impresora en otros casos.
*/
#define Condensado(f)  f<<(char)15;
#define CancelaCondensado(f) f<<(char)0x12;
#define DobleAlto(f)	 f<<(char)27<<(char)0x77<<(char)1;
#define CancelaDobleAlto(f) f<<(char)27<<(char)0x77<<(char)0;
#define DobleAncho(f) f<<(char)27<<(char)0x57<<(char)1;
#define CancelaDobleAncho(f) f<<(char)27<<(char)0x57<<(char)0;
#define EspacioEntreLineas1_8pulgadas(f) f<<(char)27<<(char)0x30<<(char)0;
#define EspacioEntreLineas7_72pulgadas(f) f<<(char)27<<(char)0x31<<(char)1;
#define EspacioEntreLineas1_6pulgadas(f)	f<<(char)27<<(char)0x32<<(char)2;
#define CPI10(f) f<<(char)0x27<<(char)0x50;
#define CPI12(f) f<<(char)0x27<<(char)0x4d;
#define SaltaPagina(f)  f<<"\f";

void ImprimirEnPapelRegistros(){
	fstream Impresora;

	if(NumVuelos==0)
		Escritorio << "No hay registros en memoria \a\a";
	else{
		Escritorio.clrscr();
		Impresora.open("LPT1", ios::out);  // LPT1 es igual a PRN
		Escritorio << "\n\nIMPRIMIENDO...";
		DobleAncho(Impresora)
		Impresora <<"\n\nRegistro  Desde   Distancia Estatura\n\n";
		CancelaDobleAncho(Impresora)
		Condensado(Impresora)
		for(int i=0; i<NumVuelos; i++){
			Impresora << setiosflags(ios::right) << setw(4) << i << "   "
								<< setiosflags(ios::left) << setw(20) << Vuelo[i].Desde
								<< setiosflags(ios::left) << setw(20) << Vuelo[i].Hacia
								<< setiosflags(ios::right) << setw(15) << Vuelo[i].Distancia
								<< endl;
		}
		CancelaCondensado(Impresora)
		SaltaPagina(Impresora);
		Impresora.close();
	}
}

void Graficarbarras(){
	int ManejadorGrafico = DETECT, ModoGrafico;
	int  izquierda, arriba=20, arribabar, ancho, abajo, profundidad, eje=10;
	float fraccion, MayorDistancia=0, Delta;

	initgraph( &ManejadorGrafico, &ModoGrafico, "\\tc\\bgi" );
	setbkcolor(BLUE);	setcolor(YELLOW);	rectangle(0, 0, getmaxx(), getmaxy());

	if( NumVuelos ){
		MayorDistancia=Vuelo[0].Distancia;
		for(int i=1; i<NumVuelos; i++)
			if(Vuelo[i].Distancia>MayorDistancia)
				MayorDistancia = Vuelo[i].Distancia;

		ancho = (int)( (getmaxx()-eje) / ((NumVuelos * 2 ) + 1) );
		abajo = getmaxy() - 30;
		profundidad = (int)(ancho / 8);
		izquierda = ancho+eje;
		setcolor(YELLOW);	settextstyle(DEFAULT_FONT, HORIZ_DIR, 2);
		outtextxy(5, abajo+10 , "Kms");

		Delta= (float)(abajo-arriba+1)/MayorDistancia;
		line(eje/2, arriba, eje/2, abajo); //eje y
		for(float rayita=abajo; rayita>=arriba-Delta; rayita-=Delta)
			line(3, (int)rayita, 7, (int)rayita);

		for( i=0; i<NumVuelos; i++){
				fraccion = (float) Vuelo[i].Distancia / MayorDistancia;
				arribabar = (int)(abajo - fraccion * (abajo-arriba) );
				setcolor(RED); setfillstyle(SOLID_FILL, MAGENTA);
				bar3d(izquierda, arribabar, (izquierda + ancho), abajo, profundidad, 1);
				setcolor(CYAN);
				settextstyle(SMALL_FONT, HORIZ_DIR, 0);// (tipo letra, direccion, tama¤o )
				outtextxy(izquierda+ancho/3, arribabar, Vuelo[i].Desde);
				outtextxy(izquierda+ancho/3, arribabar+textheight("H"), Vuelo[i].Hacia);
				izquierda += (ancho * 2);
		}
	}
	else{
		setcolor(RED); settextstyle(TRIPLEX_FONT, VERT_DIR, 7);
		outtextxy(getmaxx()/2-10, 10, "NO HAY DATOS");
	}
	getch(); closegraph();
}
/*==========================================================================*/
/*FIN DE FUNCIONES NECESARIAS PARA MANTENIMIENTO DE BASE DE                 */
/*CONOCIMIENTO DE RUTAS DE VUELOS                                           */
/*==========================================================================*/

/*==========================================================================*/
/*A CONTINUACION FUNCIONES NECESARIAS PARA BUSQUEDAS EN BASE DE CONOCIMIENTO*/
/*                                                                          */
/*Aplicaci¢n de la estructura de datos pila en T‚cnica de resoluci¢n de     */
/*problemas en Inteligencia Artificial; consistente en la implementaci¢n de */
/*los algoritmos de b£squeda de soluciones de Primero en profundidad,       */
/*Primero en anchura, sobre la abstracci¢n de un grafo dirigido.            */
/*==========================================================================*/

int Cima = 0;       //Cima de la pila de retroseguimiento
const int MaxPila=20;

struct Pila	{
	char Desde[20];
	char Hacia[20];
	int Distancia;
} PILA[MaxPila];  // Pila para devolverse en la búsqueda

void MeterEnPila(char *Desde, char *Hacia, int Distancia){

	if(Cima < MaxPila)	{
		AsignarCadena(PILA[Cima].Desde, Desde);
		AsignarCadena(PILA[Cima].Hacia, Hacia);
		PILA[Cima].Distancia = Distancia;
		Cima++;
	}
	else
		cout << "Pila llena.\n\a";
}

void SacarDePila(char *Desde, char *Hacia, int *Distancia){

	if(Cima > 0) {
		Cima--;
		AsignarCadena(Desde,PILA[Cima].Desde);
		AsignarCadena(Hacia,PILA[Cima].Hacia);
		*Distancia=PILA[Cima].Distancia;
	}
	else
		cout << "Pila vacia.\n";
}

void BorrarMarcas(){

	for(int i=0; i<NumVuelos; i++)
			Vuelo[i].Visitado=0;
}

//Se muestra la ruta y la distancia, sac ndola de la PILA
void Ruta(char *Hacia){
	int Kms=0, i=0;

	while(i < Cima)	{
		Escritorio << " " << PILA[i].Desde << "---> ";
		Kms += PILA[i].Distancia;
		i++;
	}

	if (Kms == 0)
		Escritorio << "No hay Vuelo Hacia " << Hacia;
	else {
		Escritorio << " " << Hacia << endl;
		Escritorio << "La Distancia es " << Kms << endl;
	}
}

//si hay vuelo directo entre Desde y Hacia, retorna distancia si no devuelve 0
int VueloDirecto(char *Desde, char *Hacia){
	int i;

	for(i=0; i<NumVuelos; i++)
		if(!CompararCadenas(Vuelo[i].Desde, Desde) && !CompararCadenas(Vuelo[i].Hacia,Hacia))
			return Vuelo[i].Distancia;
	return 0;	// no encontrado
}

//Dada una ciudad encuentra un  destino
int EncuentraEscala(char *Desde, char *OtraCiudad){
	int i=0;

	while(i < NumVuelos)	{
		if(!CompararCadenas(Vuelo[i].Desde, Desde)  &&	!Vuelo[i].Visitado)	{
			AsignarCadena(OtraCiudad, Vuelo[i].Hacia);
			Vuelo[i].Visitado = 1;	// se marca como visitado
			return Vuelo[i].Distancia;    //Se encontr¢ conexi¢n
		}
		i++;
	}
	return 0;  //No se encontr¢ conexi¢n
}

//Se determina si hay un vuelo entre Desde y Hacia
int RecorridoEnProfundidad(char *Desde, char *Hacia){
	int KmsVuelo, Kms;
	char OtraCiudad[20];

	if(KmsVuelo = VueloDirecto(Desde,Hacia)){	//se determina si el destino es alcanzado
		MeterEnPila(Desde,Hacia,KmsVuelo);
		return 0;
	}

	if(Kms=EncuentraEscala(Desde,OtraCiudad)){// Se intenta otra conexi¢n
		MeterEnPila(Desde, Hacia, Kms);
		RecorridoEnProfundidad(OtraCiudad,Hacia);
	}
	else
		if(Cima > 0){ // vuelta atr s, no se encontr¢ destino
			SacarDePila(Desde, Hacia, &Kms);
			RecorridoEnProfundidad(Desde, Hacia);
		}
}

int RecorridoEnAnchura(char *Desde, char *Hacia){
	int KmsHaciaEscala, KmsDesdeEscala, KmsVuelo;
	char Escala[20];

	while(KmsDesdeEscala = EncuentraEscala(Desde, Escala)) {
		if(	KmsHaciaEscala = VueloDirecto(Escala, Hacia) ) {
			MeterEnPila(Desde, Escala, KmsDesdeEscala);
			MeterEnPila(Escala, Hacia, KmsHaciaEscala);
			return 0;
		}
	}
	if(KmsDesdeEscala = EncuentraEscala(Desde, Escala)){//Se intenta si hay una conexi¢n
		MeterEnPila(Desde,Escala,KmsDesdeEscala);
		RecorridoEnAnchura(Escala, Hacia);
	}
	else
		if(Cima > 0){
			SacarDePila(Desde,Hacia, &KmsDesdeEscala);
			RecorridoEnAnchura(Desde,Hacia);
		}
}

//Dada una ciudad encuentra un  destino en la escalada de la colina
int EncuentraEnEscaladaColina(char *Desde, char *OtraCiudad){
	int EncuentraPos=0, MayorKms=0, PosMayorKms=-1;

	while(EncuentraPos < NumVuelos)	{
		if(!CompararCadenas(Vuelo[EncuentraPos].Desde, Desde)  &&	!Vuelo[EncuentraPos].Visitado)
			if(Vuelo[EncuentraPos].Distancia>MayorKms){
				PosMayorKms = EncuentraPos;
				MayorKms = Vuelo[EncuentraPos].Distancia;
			}
		EncuentraPos++;
	}
	if(PosMayorKms>-1){
			AsignarCadena(OtraCiudad, Vuelo[PosMayorKms].Hacia);
			Vuelo[PosMayorKms].Visitado = 1;	// se marca como visitado
			return Vuelo[PosMayorKms].Distancia;    //Se encontr¢ conexi¢n
	}
	return 0;  //No se encontr¢ conexi¢n
}

int RecorridoEnProfundidadConEscaladaColina(char *Desde, char *Hacia){
	int KmsVuelo, Kms;
	char OtraCiudad[20];

	if(KmsVuelo = VueloDirecto(Desde,Hacia)){	//se determina si el destino es alcanzado
		MeterEnPila(Desde,Hacia,KmsVuelo);
		return 0;
	}

	if(Kms=EncuentraEnEscaladaColina(Desde,OtraCiudad)){// Se intenta otra conexi¢n
		MeterEnPila(Desde, Hacia, Kms);
		RecorridoEnProfundidadConEscaladaColina(OtraCiudad,Hacia);
	}
	else
		if(Cima > 0){ // vuelta atr s, no se encontr¢ destino
			SacarDePila(Desde, Hacia, &Kms);
			RecorridoEnProfundidadConEscaladaColina(Desde, Hacia);
		}
}

//Dada una ciudad encuentra un  destino en la b£squeda del menor-coste
int EncuentraEnMenorCoste(char *Desde, char *OtraCiudad){
	int EncuentraPos=0, MenorKms=32767, PosMenorKms=-1;

	while(EncuentraPos < NumVuelos)	{
		if(!CompararCadenas(Vuelo[EncuentraPos].Desde, Desde)  &&	!Vuelo[EncuentraPos].Visitado)
			if(Vuelo[EncuentraPos].Distancia<MenorKms){
				PosMenorKms = EncuentraPos;
				MenorKms =Vuelo[EncuentraPos].Distancia;
			}
		EncuentraPos++;
	}
	if(PosMenorKms>-1){
			AsignarCadena(OtraCiudad, Vuelo[PosMenorKms].Hacia);
			Vuelo[PosMenorKms].Visitado = 1;	// se marca como visitado
			return Vuelo[PosMenorKms].Distancia;    //Se encontr¢ conexi¢n
	}
	return 0;  //No se encontr¢ conexi¢n
}

int RecorridoEnProfundidadConMenorCoste(char *Desde, char *Hacia){
	int KmsVuelo, Kms;
	char OtraCiudad[20];

	if(KmsVuelo = VueloDirecto(Desde,Hacia)){	//se determina si el destino es alcanzado
		MeterEnPila(Desde,Hacia,KmsVuelo);
		return 0;
	}

	if(Kms=EncuentraEnMenorCoste(Desde,OtraCiudad)){// Se intenta otra conexi¢n
		MeterEnPila(Desde, Hacia, Kms);
		RecorridoEnProfundidadConMenorCoste(OtraCiudad,Hacia);
	}
	else
		if(Cima > 0){ // vuelta atr s, no se encontr¢ destino
			SacarDePila(Desde, Hacia, &Kms);
			RecorridoEnProfundidadConMenorCoste(Desde, Hacia);
		}
}

void Recorridos(){
	char Desde[20], Hacia[20],AuxDesde[20], AuxHacia[20];

	Escritorio.window(1,1, 80,25);
	textbackground (CYAN);	textcolor (BLACK);
	Escritorio.clrscr();
	if(NumVuelos){
		Escritorio << "Desde? ";	gets(Desde);	Apropiado(Desde);
		Escritorio << "Hacia? ";	gets(Hacia);	Apropiado(Hacia);

		if(!CompararCadenas(Desde, Hacia))
			Escritorio << "Por favor, est  en la misma ciudad, llame un Taxi ...";
		else{
			Cima=0; BorrarMarcas();
			Escritorio << " \n\nRecorrido en Anchura: \n";
			AsignarCadena(AuxDesde, Desde);		AsignarCadena(AuxHacia, Hacia);
			RecorridoEnAnchura(AuxDesde, AuxHacia);
			Ruta(Hacia);

			Cima=0; BorrarMarcas();
			Escritorio << " \n\nRecorrido en Profundidad: \n";
			AsignarCadena(AuxDesde, Desde);		AsignarCadena(AuxHacia, Hacia);
			RecorridoEnProfundidad(AuxDesde, AuxHacia);
			Ruta(Hacia);

			Cima=0; BorrarMarcas();
			Escritorio << " \n\nRecorrido en Profundidad con Escalada de Colina: \n";
			AsignarCadena(AuxDesde, Desde);		AsignarCadena(AuxHacia, Hacia);
			RecorridoEnProfundidadConEscaladaColina(AuxDesde, AuxHacia);
			Ruta(Hacia);

			Cima=0; BorrarMarcas();
			Escritorio << " \n\nRecorrido en Profundidad con Menor-Coste: \n";
			AsignarCadena(AuxDesde, Desde);		AsignarCadena(AuxHacia, Hacia);
			RecorridoEnProfundidadConMenorCoste(AuxDesde, AuxHacia);
			Ruta(Hacia);
		}
	}
	else
		Escritorio << "No hay registros en memoria\a";

	getch(); Escritorio.window(1,2, 80,24);
}

void EliminarVuelo(char *Desde, char *Hacia){
	int i=0;

	while(i < NumVuelos)	{
		if(!CompararCadenas(Vuelo[i].Desde, Desde)  &&
			 !CompararCadenas(Vuelo[i].Hacia, Hacia) 	)
		{
			AsignarCadena(Vuelo[i].Desde, "");
			return;
		}
		i++;
	}
}

void EliminacionDeNodos(){
	char Desde[20], Hacia[20],AuxDesde[20], AuxHacia[20], C1[20], C2[20];
	int Distancia;

	Escritorio.window(1,1, 80,25);
	textbackground (CYAN);	textcolor (BLACK);
	Escritorio.clrscr();
	if(NumVuelos){
		Escritorio << "Desde? ";	gets(Desde);	Apropiado(Desde);
		Escritorio << "Hacia? ";	gets(Hacia);	Apropiado(Hacia);

		if(!CompararCadenas(Desde, Hacia))
			Escritorio << "Por favor, est  en la misma ciudad, llame un Taxi ...";
		else{
			Escritorio << "Digitar Esc para terminar ...";

			do{
				Cima=0;
				Escritorio << " \n\nRecorrido en Profundidad: \n";
				AsignarCadena(AuxDesde, Desde);		AsignarCadena(AuxHacia, Hacia);
				RecorridoEnProfundidad(AuxDesde, AuxHacia);
				Ruta(Hacia);
				BorrarMarcas();
				if(Cima>0) SacarDePila(C1, C2, &Distancia);
					EliminarVuelo(C1, C2);//Saca el £ltimo nodo de la base de datos
				Escritorio << "Por favor insista. Digitar Esc para terminar ...";
			}while(getch()!=27);
		}
	}
}

void EliminacionDeCaminos(){
	char Desde[20], Hacia[20],AuxDesde[20], AuxHacia[20];

	Escritorio.window(1,1, 80,25);
	textbackground (CYAN);	textcolor (BLACK);
	Escritorio.clrscr();
	if(NumVuelos){
		Escritorio << "Desde? ";	gets(Desde);	Apropiado(Desde);
		Escritorio << "Hacia? ";	gets(Hacia);	Apropiado(Hacia);
		AsignarCadena(AuxDesde, Desde);	 AsignarCadena(AuxHacia, Hacia);
		if(!CompararCadenas(Desde, Hacia))
			Escritorio << "Por favor, est  en la misma ciudad, llame un Taxi ...";
		else{
			BorrarMarcas();
			Escritorio << "Digitar Esc para terminar ...";
			do{
				Cima=0;
				Escritorio << " \n\nRecorrido en Profundidad: \n";
				RecorridoEnProfundidad(AuxDesde, AuxHacia);
				Ruta(Hacia);
				Escritorio << "Por favor insista. Digitar Esc para terminar ...";
			} while(getch()!=27);
		}
	}
}

void SolucionOptima(){


}
/*==========================================================================*/
/*TERMINAN FUNCIONES NECESARIAS PARA MANTENIMIENTO DE BASE DE               */
/*CONOCIMIENTO DE RUTAS DE VUELOS                                           */
/*==========================================================================*/

/*==========================================================================*/
/*A CONTINUACION FUNCIONES NECESARIAS PARA MANIPULACION DEL MOUSE           */
/*Se utilizan funciones de la interrupci¢n 33 INT33                         */
/*==========================================================================*/
int IniciaMouse( int &BotonMouse){
	union REGS entra,sale;
	entra.x.ax = 0x0000;
	int86( 0x33, &entra, &sale);
	BotonMouse = sale.x.bx;
	return ( sale.x.ax );
}
//**************************************************************************
void MuestraMouse( void ){
 union REGS entra, sale;
 entra.x.ax = 0x0001;
 int86 ( 0x33, &entra, &sale );
}
//**************************************************************************
void EscondeCursorMouse( void ){
 union REGS entra, sale;
 entra.x.ax = 0x0002;
 int86( 0x33, &entra, &sale);
}
//**************************************************************************
int LeerTeclaXYMouse( int &x, int &y){
 union REGS entra,sale;
 entra.x.ax = 0x0003;
 int86( 0x33, &entra, &sale );
 x = sale.x.cx;
 y = sale.x.dx;
 return(sale.x.bx);//Bot¢n: 0=no pulsado; 1=izquierdo; 2=derecho; 4=central.
}
/*==========================================================================*/
/*TERMINAN FUNCIONES NECESARIAS PARA MANIPULACION DEL MOUSE                 */
/*==========================================================================*/

/*==========================================================================*/
/* FUNCIONES NECESARIAS PARA EL MANEJO DE CADENAS DE CARACTERES             */
/*==========================================================================*/
//La siguiente funci¢n reemplaza a strcmp del archivo a incluir string.h
//---------------------------------------------------------------------------
int CompararCadenas(char *cadena1, char *cadena2)
{
	int pos=1;
	while(*cadena1==*cadena2)
	{
		if(*cadena1=='\0' && *cadena2=='\0') //Las dos cadenas son iguales
			return 0;
		cadena1++;
		cadena2++;
		pos++;
	}
	if(*cadena1<*cadena2)
		pos = -pos;
	return pos;
}
//---------------------------------------------------------------------------
//La siguiente funci¢n reemplaza a strcpy del archivo a incluir string.h
void AsignarCadena(char *cadena2, char *cadena1){

	while(*cadena1){
		*cadena2 = *cadena1;
		cadena2++;
		cadena1++;
	}
	*cadena2 = *cadena1;  //Siempre debe ser '\0' lo que asigne aqu¡
}
//---------------------------------------------------------------------------
//Similar a la funci¢n strlen de string.h
int LongitudCadena(char *cadena){
	int c=0;

	while(*cadena++)
		c++;
	return c;
}
//---------------------------------------------------------------------------
//Esta funci¢n reemplaza a toupper de la librer¡a string.h
char AMayuscula(char c){

	if(c>=97 && c<=122)
		c -= (97-65);
	return c;
}
//---------------------------------------------------------------------------
//esta funci¢n reemplaza a tolower de la librer¡a string.h
char AMinuscula(char c){

	if(c>=65 && c<=90)
		c += (97-65);
	return c;
}
//---------------------------------------------------------------------------
void EliminarEspaciosAlInicio(char *c){
	char *p;
	while(*c==' '){
		p=c;
		while(*p){
			*p = *(p+1);
			p++;
		}
	}
}
//---------------------------------------------------------------------------
//La siguiente funci¢n convierte la letra inicial de cada palabra de una
//cadena en may£scula y el resto en min£sculas.
void Apropiado(char *c){
	while(*c){
	*c = AMayuscula(*c);
	c++;
	while(*c && *c!=' '){
		*c = AMinuscula(*c);
		c++;
	}
	while(*c && *c==' ')
		c++;
	}
}
/*==========================================================================*/
/* FIN DE FUNCIONES PARA MANEJO DE CARACTERES                               */
/*==========================================================================*/

/*==========================================================================*/
/*A CONTINUACION FUNCIONES NECESARIAS PARA MANEJO DEL MENU PRINCIPAL Y DE   */
/*LOS SUBMENUS                                                              */
/*==========================================================================*/
//----------------------------------------------------------------------------
//        LA CLASS PARA CONSTRUIR UN MENU DE CONMUTADORES VERTICAL
//----------------------------------------------------------------------------
const int MaxMenu=10;  //M ximo permitido por cualquier men£

class MENU_VERTICAL {
	int pos;
	int MaxOpciones;//M ximo de cada men£ particular, el m ximo es MaxMenu que es global
	char *Opcion[MaxMenu];  //Palabras que compondr n cada men£
	char *Comenta[MaxMenu]; //Comentario de cada opci¢n del men£
	char *MensajeAyuda; //Mensaje que utiliza la funci¢n Men£Ayudas
	char Pantalla[4000];  //Almacenar  caracteres de la pantalla con atributos
	int LargoCad, X, Y;

public:

	MENU_VERTICAL(int MiMax,         //funci¢n constructora
								char *Op[MaxMenu],
								char Com[MaxMenu][60],
								char *Ayuda,
								char Columna,
								char Fila
							);
	void MueveVert(int MaxOp, int Fondo, int Color, int LargoCad,
								 int pos, int X, int Y, char *p, char *Comentario);
	int Principal ();

	//A continuaci¢n se definen variables "amigas"(friend). Estas no son miembros
	//de la class MENU_VERTICAL, pero pueden con esta declaraci¢n, acceder a la
	//parte privada de ella(la class MENU_VERTICAL).
	friend void LineaFinal(char *Cad);//Funciones
	friend void Ayuda(char *Cad);
	friend void Marco(int Xo,int Yo, int Xf, int Yf, int Color);
};
//----------------------------------------------------------------------------
MENU_VERTICAL::MENU_VERTICAL(	int MiMax,
														
	char *Op[MaxMenu],
														
	char Com[MaxMenu][60],
														
	char *Ayuda,

	char Columna,

	char Fila
													)
{	int TeclaMouse;

	X=Columna;//Se asignan valores a identificadores privados a la class MENU_VERTICAL
	Y=Fila;
	pos=0;
	MaxOpciones=MiMax;
	for(int i=0; i<MiMax; i++){
		Opcion[i] =Op[i] ;
		Comenta[i] = Com[i] ;
	}
	MensajeAyuda = Ayuda;

	LargoCad=LongitudCadena(Op[0]);
	for(i=1; i<MaxOpciones; i++)
		if(LongitudCadena(Op[i]) > LargoCad)
			LargoCad=LongitudCadena(Op[i]);    //Calcula la cadena m s larga
	LargoCad+=2; //Los espacios en blanco de cada lado de la cadena

	LineaFinal("Esc:Volver  Alt-X:Salir.");
	if(X+LargoCad+2>=80) //El marco del men£ se saldr¡a de la pantalla
		X = 80-(LargoCad+2);
	Menu.window(X-1,Y+1,X+LargoCad+2,Y+MaxOpciones+2);
	textbackground(BLACK); Menu.clrscr();

	Marco(X-2,Y,X+LargoCad+1,Y+MaxOpciones+1,WHITE);
	for (i=0; i < MaxOpciones; i++) {
		MueveVert(MaxOpciones, C1, C2, LargoCad, i, X, Y, Op[i], Com[i]);
	}
	gettext(1, 1, 80, 25, Pantalla);
}
//----------------------------------------------------------------------------
void MENU_VERTICAL::MueveVert(int MaxOp, int Fondo, int Color, int LargoCad,
													int pos, int X, int Y, char *p, char *Comentario) {
	pos+=2; //Este cambio es solo local a esta funci¢n
	EscondeCursorMouse();
	Menu.window(X,Y,X+LargoCad,Y+MaxOp);
	textbackground (Fondo);	textcolor (Color);
	gotoxy(1, pos);
	for(int i=1; i<=LargoCad; i++)
		Menu << " ";
	gotoxy(2, pos); Menu << p;
	textcolor(C4);
	gotoxy(2, pos); Menu << p[0];
	Menu.window(23,25,80,25);
	_setcursortype(_NOCURSOR);
	textbackground(C1);	textcolor(C2);Menu.clrscr();
	Menu << "³ " << Comentario ;
	MuestraMouse();
}
//----------------------------------------------------------------------------
int MENU_VERTICAL::Principal () {
	int i, TeclaMouse=0, x, y, Invocar=1;
	char c, *p;

	do{
		if(Invocar){
			Invocar=0;
			puttext(1, 1, 80, 25, Pantalla);
			_setcursortype(_NOCURSOR); MuestraMouse();
			MueveVert(MaxOpciones,C3,C2,LargoCad,pos,X,Y,Opcion[pos],Comenta[pos]);
		}
		do{
			TeclaMouse = LeerTeclaXYMouse(x,y);
		} while (!kbhit() && !TeclaMouse);
		if(!TeclaMouse){
			c = getch();
			if (c == 0) {
				c = getch();
				switch (c) {
					case Abj: MueveVert(MaxOpciones,C1,C2,LargoCad,pos,X,Y,Opcion[pos],Comenta[pos]);
										pos++;
										if (pos == MaxOpciones)
											pos=0;
										MueveVert(MaxOpciones,C3,C2,LargoCad,pos,X,Y,Opcion[pos],Comenta[pos]);
										break;
					case Arr:	MueveVert(MaxOpciones,C1,C2,LargoCad,pos,X,Y,Opcion[pos],Comenta[pos]);
										pos--;
										if (pos == -1)
											pos = MaxOpciones-1;
										MueveVert(MaxOpciones,C3,C2,LargoCad,pos,X,Y,Opcion[pos],Comenta[pos]);
										break;
					case Izq: puttext(1, 1, 80, 25, Pantalla); return -3;
					case Der: puttext(1, 1, 80, 25, Pantalla); return -2;
					case  AltX:	exit(0); //Alt-X
					case  F1:	Ayuda(MensajeAyuda); //F1
										break;
				}
			} else {
				if(c==Esc){
					EscondeCursorMouse();
					puttext(1, 1, 80, 25, Pantalla);
					MuestraMouse();
					return -1;
				}
				else
					if(c==Entrar)
						Invocar = 1;
					else{
						c=AMayuscula(c);
						i=0;
						while( c!=Opcion[i][0]  &&	i<MaxOpciones)
								i++;
						if(i<MaxOpciones){// Se digit¢ letra inicial de opci¢n
							pos = i;
							Invocar=1;
						}
					}
			}
		} else
		if(TeclaMouse){
			if((y>=Y*8 && y<(Y+MaxOpciones)*8) && (x>(X-2)*8 && x<(X+LargoCad-1)*8)){
				MueveVert(MaxOpciones,C1,C2,LargoCad,pos,X,Y,Opcion[pos], Comenta[pos]);
				pos = (y-(Y-1)*8) / 8 - 1;	Invocar=1;
				MueveVert(MaxOpciones,C3,C2,LargoCad,pos,X,Y,Opcion[pos],Comenta[pos]);
			}
			else
			if(!(x>=(X-3)*8 && y>(Y-2)*8 && x<=(X+LargoCad)*8 &&y<=(Y+MaxOpciones)*8)){
				EscondeCursorMouse();
				puttext(1, 1, 80, 25, Pantalla); MuestraMouse();
				return -1; //Se hizo click fuera del cuadro del men£.
			}
		}

		if (Invocar){
			EscondeCursorMouse();
			Menu.clrscr();
			MueveVert(MaxOpciones, C1, C2, LargoCad, pos, X, Y, Opcion[pos],
					 "Digite Esc para salir......                        ");
			MuestraMouse();
			return pos;
		}
	} while(pos>=0);
	return pos;
}
//---------------------------------------------------------------------------
// Definicion de funciones amigas(friend).
// Observe que no se definen como miembros de alguna class
// Estas son necesarias para el manejo del menu vertical y el horizontal
// Ellas pueden, de esta forma, ser compartidas por varias clases
//---------------------------------------------------------------------------
void Marco(int Xo,int Yo, int Xf, int Yf, int Color){
	const arrizq=201;
	const arrder=187;
	const abajizq=200;
	const abajder=188;
	const vert=186;
	const horiz=205;
	int i;

	Ventanita.window (Xo+1,Yo+1,Xf+1,Yf+1);
	textbackground(BLACK); Ventanita.clrscr();
	Ventanita.window (Xo,Yo,Xf,Yf);
	textbackground (Color);	textcolor (BLACK); Ventanita.clrscr();
	Xf -= Xo;       //coordenadas relativas a Ventanita
	Yf -= Yo-1;
	Xo =  2; Yo = 1;
	gotoxy (Xo,Yo);	Ventanita <<(char)arrizq;
	gotoxy (Xf,Yo);	Ventanita<<(char)arrder;
	gotoxy (Xo,Yf);	Ventanita<<(char)abajizq;
	gotoxy (Xf,Yf);	Ventanita<<(char)abajder;
	for (i=Xo+1; i < Xf; i++){
		gotoxy (i,Yo); Ventanita<<(char)horiz;
		gotoxy (i,Yf); Ventanita<<(char)horiz;
	}
	for (i=Yo+1; i < Yf; i++) {
		gotoxy (Xo,i);	Ventanita<<(char)vert;
		gotoxy (Xf,i);	Ventanita<<(char)vert;
	}
}
//----------------------------------------------------------------------------
void LineaFinal(char *Cad){
	Ventanita.window(1,25,80,25);
	textbackground (WHITE); textcolor (MAGENTA); Ventanita.clrscr();
	Ventanita<< Cad;
}
//----------------------------------------------------------------------------
void Ayuda(char *Cad){
	char buffer[4096];
	gettext(1, 1, 80, 25, buffer);
	Marco(18,4,62,21,C4);
	Ventanita.window(20,5,60,20);
	textbackground (C4); textcolor (C2);

	Ventanita << Cad;
	if(getch()==0) getch();
	puttext(1, 1, 80, 25, buffer);
}
//---------------------------------------------------------------------------
//SubMenuListados
//---------------------------------------------------------------------------
const MaxMenuListados=3;
char *Op1Listados[MaxMenuListados] = { "Listar en pantalla",
						"Imprimir en papel",
						"Graficar barras"
						 };
char Com1Listados[MaxMenuListados][60] = {
					"Listado en pantalla                                    ",
					"Listar en impresora                                    ",
					"Gr fica de barras                                      "
									};
char *AyudaListados="\nEste programa fue construido por\nHumberto Mazuera P rraga\n";

int SubMenuListados(int X, int Y){
	MENU_VERTICAL Menu(MaxMenuListados, Op1Listados, Com1Listados, AyudaListados, X, Y);
	int pos=0;

	while( pos>=0 ){
		pos = Menu.Principal();
		switch (pos) {
				case 0: ListarVector(); break;
				case 1: ImprimirEnPapelRegistros(); break;
				case 2: Graficarbarras(); break;
		}
	}

	if(pos==-3) pos=-1;  //Se pulso tecla izqierda
	else
	if(pos==-2) pos=1;   //Se pulso tecla derecha
	else pos=0;          //Se pulso Esc o click fuera del men£

	return(pos);
}
//----------------------------------------------------------------------------
//     termina definici¢n del submenuListados
//----------------------------------------------------------------------------

//---------------------------------------------------------------------------
//SubMenu1: de mantenimiento de la base de conocimiento vuelos
//---------------------------------------------------------------------------
const MaxMenu1=7;
char *Op1[MaxMenu1] = { "Capturar Vuelo",
				"Mostrar informaci¢n   ->",
				"Ordenar",
				"Hallar un registro",
				"Eliminar",
				"Modificar",
				"Borrar archivo",
										 };
char Com1[MaxMenu1][60] =	{ "Se lee por teclado  un registro",
					"Se lista en pantalla, impresora y se grafica",
					"Clasificaci¢n de los datos en memoria",
					"Encontrar a partir de una clave un registro",
					"Borrar a partir de la b£squeda de una clave un registro",
					"Modificar un registro a partir de la b£squeda por clave",
					"Borrar la base de conocimiento totalmente"
									};
char *Ayuda1="\nEste programa fue construido por\nHumberto Mazuera P rraga\n";

int SubMenu1(int X, int Y){
	MENU_VERTICAL Menu(MaxMenu1, Op1, Com1, Ayuda1, X, Y);
	int pos=0;

	while( pos>=0 ){
		pos = Menu.Principal();
		switch (pos) {
				case 0: CapturarVuelo(); break;
				case 1: pos+=SubMenuListados(X+LongitudCadena(Op1[pos])+3, Y+1+pos);
								break;
				case 2: OrdenarVuelosDesde(); break;
				case 3: EncontrarRegistro();    break;
				case 4: EliminarRegistro(); break;
				case 5: ModificarRegistro();	break;
				case 6: unlink(NombreArchivo); NumVuelos=0; break;
		}
	}

	if(pos==-3) pos=-1;  //Se pulso tecla izqierda
	else
	if(pos==-2) pos=1;   //Se pulso tecla derecha
	else pos=0;          //Se pulso Esc o click fuera del men£

	return(pos);
}
//----------------------------------------------------------------------------
//     termina definici¢n del submenu1
//----------------------------------------------------------------------------

//---------------------------------------------------------------------------
//SubMenuMultiples
//---------------------------------------------------------------------------
const MaxMenuMultiples=2;
char *Op1Multiples[MaxMenuMultiples] = { "Caminos, eliminaci¢n de",
					 "Nodos, elimnaci¢n de",
				 };
char Com1Multiples[MaxMenuMultiples][60] = {
		"M‚todo de generaci¢n de m£ltiples soluciones",
		"M‚todo de generaci¢n de m£ltiples soluciones",
	 };
char *AyudaMultiples="\nEste programa fue construido por\nHumberto Mazuera P rraga\n";

int SubMenuMultiples(int X, int Y){
	MENU_VERTICAL Menu(MaxMenuMultiples, Op1Multiples, Com1Multiples, AyudaMultiples, X, Y);
	int pos=0;

	while( pos>=0 ){
		pos = Menu.Principal();
		switch (pos) {
				case 0: EliminacionDeCaminos(); break;
				case 1: EliminacionDeNodos(); break;
		}
	}

	if(pos==-3) pos=-1;  //Se pulso tecla izqierda
	else
	if(pos==-2) pos=1;   //Se pulso tecla derecha
	else pos=0;          //Se pulso Esc o click fuera del men£

	return(pos);
}
//---------------------------------------------------------------------------
//SubMenu2: de b£squedas de soluciones
//---------------------------------------------------------------------------
const MaxMenu2=3;
char *Op2[MaxMenu1] = { "Una soluci¢n",
				"Multiples Soluciones  ->",
				"Soluci¢n Optima"
											};
char Com2[MaxMenu2][60] =	{ "Profundidad, anchura, escalada y menor coste",
					"Eliminaci¢n de caminos y eliminaci¢n de nodos",
					"Se aplica una, indeseable, b£squeda exhaustiva"
					};
char *Ayuda2="\nEste programa fue construido por\nHumberto Mazuera P rraga\n";

int SubMenu2(int X, int Y){
	MENU_VERTICAL Menu(MaxMenu2, Op2, Com2, Ayuda2, X, Y);
	int pos=0;

	while( pos>=0 ){
		pos = Menu.Principal();
		switch (pos) {
				case 0: Recorridos(); break;
				case 1: pos+=SubMenuMultiples(X+LongitudCadena(Op2[pos])+3, Y+1+pos);
					break;
				case 2: SolucionOptima();
		}
	}

	if(pos==-3) pos=-1;  //Se pulso tecla izqierda
	else
	if(pos==-2) pos=1;   //Se pulso tecla derecha
	else pos=0;          //Se pulso Esc o click fuera del men£

	return(pos);
}
//----------------------------------------------------------------------------
//     termina definici¢n del submenu1
//----------------------------------------------------------------------------

//============================================================================
//             MENU DE CONMUTADORES HORIZONTALES
//----------------------------------------------------------------------------
void MueveHori(int Fondo, int Color, int x, char *p, char *Comentario){
	EscondeCursorMouse();
	Menu.window(1,1,80,1);
	textbackground (Fondo);	textcolor (Color);
	gotoxy(x,1); Menu << " " << p << " ";
	textcolor (C4);
	gotoxy(x+1,1); Menu << p[0];
	Menu.window(23,25,80,25);
	_setcursortype(_NOCURSOR);
	textbackground(C1);	textcolor (C2); Menu.clrscr();
	Menu << "³ " << Comentario ;
	MuestraMouse();
}
//----------------------------------------------------------------------------
void main() {
	const int MaxOp=3;       //Cantidad M xima de opciones en el men£
	int i, j, c, pos=0, TeclaMouse=0, x, y, Invocar=1;
	char Pantalla[4000];//80*25 *2
	char *Op[MaxOp] = {"Vuelos","B£squedas","Salir" };
	int XOp[MaxOp];
	char *Cm[MaxOp] =	{	"Mantenimiento Base Conocimiento Vuelos",
					"Recorridos en anchura, profundidad, etc",
					"Termina el programa y salir al sistema operativo"
										};
	char *MensajeAyuda="\nEste programa fue construido por\nHumberto Mazuera Párraga\
									\nhmazuera@cuao.edu.co";
	if ( !IniciaMouse(TeclaMouse) ) {
		cout << "El rat¢n NO est  instalado" << endl;
		delay(2000);
		exit(1);
	}

	XOp[0]= 3;
	for (i=1; i < MaxOp; i++)
		XOp[i] = XOp[i-1]+LongitudCadena(Op[i-1]) + 2;
	Escritorio.window(1,2,80,24); textbackground(BLUE); Escritorio.clrscr();
	LineaFinal("F1: Ayuda Alt-X: Salir.  Digite letra inicial de Opci¢n");
	Menu.window(1, 1, 80, 1);
	textbackground(C1);
	Menu.clrscr();

	for (i=0; i < MaxOp; i++)
		MueveHori(C1, C2, XOp[i], Op[i], Cm[i]);
	gettext(1, 1, 80, 25, Pantalla);

	LeerArchivoYCargarEnVector();

	for(;;){
		if(Invocar){
			Invocar=0;
			puttext(1, 1, 80, 25, Pantalla);
			_setcursortype(_NOCURSOR); MuestraMouse();
			MueveHori(C3, C2, XOp[pos], Op[pos], Cm[pos]);
		}
		do{
			TeclaMouse = LeerTeclaXYMouse(x,y);
		} while (!kbhit() && !TeclaMouse);

		if(!TeclaMouse){
			c = getch();
			if (c == 0) {
				c = getch();
				switch (c) {
					case Der:MueveHori(C1, C2, XOp[pos], Op[pos], Cm[pos]);
								pos++;
								if (pos == MaxOp)	pos=0;
								MueveHori(C3,C2,XOp[pos],Op[pos], Cm[pos]);
								break;
					case Izq:MueveHori(C1, C2, XOp[pos], Op[pos], Cm[pos]);
								pos--;
								if (pos == -1) pos = MaxOp-1;
								MueveHori(C3,C2,XOp[pos],Op[pos],Cm[pos]);
								break;
					case AltX:	exit(0); //Alt-X
					case F1:	Ayuda(MensajeAyuda); //F1
				}
			}
			else {
				if(c==Esc)
					return;
				else
					if(c==Entrar)
						Invocar = 1;
					else{
						c=AMayuscula(c);
						i=0;
						while( c!=Op[i][0]  &&	i<MaxOp)
								i++;
						if(i<MaxOp){// Se digit¢ letra inicial de opci¢n
							pos = i;
							Invocar=1;
						}
					}
			}
		} else
		if(TeclaMouse && y<8){
			i=0;
			while(i<MaxOp &&
						 ! ( x >= ( XOp[i]-1 ) * 8  &&
							 x < ( XOp[i] + LongitudCadena(Op[i])+1 ) * 8)
						)
				 i++;
			if(i<MaxOp){ // Se hizo "click" en recuadro del men£
				MueveHori(C1, C2, XOp[pos], Op[pos], Cm[pos]);
				pos=i; Invocar=1;
				MueveHori(C3, C2, XOp[pos], Op[pos], Cm[pos]);
			}
		}

		if (Invocar){
			switch (pos) {
				case 0: pos+=SubMenu1(XOp[pos], 2);	break;
				case 1: pos+=SubMenu2(XOp[pos], 2);	break;
				case 2: GrabarVectorEnArchivo();		return;
			}
		}
		TeclaMouse=0; c=0;
	}//for(;;);
}

