el cartero
Publicado por miguel (1 intervención) el 20/04/2005 01:28:01
PROBLEMA
El cartero de una zona campestre debe entregar cartas en N de las casas de la región. Para ello, desea armarse un recorrido que le permita entregar todas las cartas y regresar a su oficina.
El desea que el trayecto entre dos casas consecutivas sea siempre recto (Horizontal y Vertical). Como le gusta pasear pretende, además, que el recorrido no se "corte", esto es que todas las casas queden conectadas.
El problema consiste en escribir un programa que permita el ingreso de las coordenadas (X,Y) de cada una de las N casas y de la Oficina de Correos y que, si existe, encuentre un recorrido que satisfaga los deseos del cartero emitiendo finalmente una lista de las casas en el orden en que deben ser visitadas.
un ejemplo: Datos de Entrada:
Casa 1: (0,1)
Casa 2: (2,3)
Casa 3: (0,3)
Casa 4: (1,3)
Casa 5: (2,2)
Casa 6: (0,2)
Casa 7: (0,0)
Oficina: (1,0)
la respuesta seria: Salida: Oficina, Casa 7, Casa 1, Casa 6, Casa 3, Casa 4, Casa 2, Casa 5, Oficina
de la oficina a la primera casa puede ser el recorrido en diagonal... pero las casassi son en horizontal y vetical, la matriz donde se ponen las casas es cuadratica y se le pide al usuario.....
Por favor demen unas sugerencias pa resolver este problema porq estoy desesperado y no he podido...........
El cartero de una zona campestre debe entregar cartas en N de las casas de la región. Para ello, desea armarse un recorrido que le permita entregar todas las cartas y regresar a su oficina.
El desea que el trayecto entre dos casas consecutivas sea siempre recto (Horizontal y Vertical). Como le gusta pasear pretende, además, que el recorrido no se "corte", esto es que todas las casas queden conectadas.
El problema consiste en escribir un programa que permita el ingreso de las coordenadas (X,Y) de cada una de las N casas y de la Oficina de Correos y que, si existe, encuentre un recorrido que satisfaga los deseos del cartero emitiendo finalmente una lista de las casas en el orden en que deben ser visitadas.
un ejemplo: Datos de Entrada:
Casa 1: (0,1)
Casa 2: (2,3)
Casa 3: (0,3)
Casa 4: (1,3)
Casa 5: (2,2)
Casa 6: (0,2)
Casa 7: (0,0)
Oficina: (1,0)
la respuesta seria: Salida: Oficina, Casa 7, Casa 1, Casa 6, Casa 3, Casa 4, Casa 2, Casa 5, Oficina
de la oficina a la primera casa puede ser el recorrido en diagonal... pero las casassi son en horizontal y vetical, la matriz donde se ponen las casas es cuadratica y se le pide al usuario.....
Por favor demen unas sugerencias pa resolver este problema porq estoy desesperado y no he podido...........
Valora esta pregunta
0