Tema: Ejercicio
Ver Mensaje Individual
  #1 (permalink)  
Antiguo 30/10/2011, 23:01
AlanFC
 
Fecha de Ingreso: septiembre-2011
Mensajes: 42
Antigüedad: 12 años, 7 meses
Puntos: 3
Ejercicio

Bueno, este ejercicio me salio en una competencia que fui de programacion en Python, y no logre realizarlo...

Determinar el costo del camino más corto para que un robot escape de un mapa. Estos son de la forma:
##..
.R#.
...#
.....

En este caso el mapa es de tamaño 4x4. Los puntos "." corresponden a espacios vacios o disponibles, el signo "#" señala un obstaculo por el cual se no se puede pasar y la letra "R" corresponde a un robot. Las reglas para moverse son sencillas:
- El robot puede moverse solo en linea recta, sin doblar.
- Se puede avanzar en direccion horizontal, vertical y adiagonal.
- No se puede atravesar los obstaculos "#"
- Para salir del mapa es necesario llegara a algun limite del mapa.

En el siguiente mapa de 5x5 se señala con la letra "x" los posibles caminos que puede tomar "R":
##x.x
.xxx.
xxRxx
.xxx.
x.#.x

Tu tarea consiste en, dado un mapa, determinar el costo del camino más corto para que R pueda salur de el. El camino escogido debe ser en linea recta hacia la salida, ya que R aun no sabe como doblar de manera eficaz.
Cita:
Entrada de datos:
Tu programa recibira en la primrea linea un entero 0<n<50 correspondiente al tamaño del mapa (n x n). En las siguientes n lineas habaran n caracteres en cada una, correspondientes a los objetos del mapa. No habra más de un robot por mapa.
Salida de datos:
Tu programa debe mostrar por panatlla un numero entero correspondiente al menor costo necesario para que R salga del mapa. En este caso de no existir salida se debe mostrar por pantalla el numero -1.
Ejemplo:
Entrada:
5
##...
......
..R..
.....
..#..

Salida:
2

Mi codigo bastante asqueroso fue el siguiente...
Código Python:
Ver original
  1. a = input ()
  2. lista = []
  3. for A in range (a):
  4.     lista2 = []
  5.     b = raw_input ()
  6.     for B in range(a):
  7.         lista2.append(b[B])
  8.         if b[B]=="R":
  9.             y,x = (A,B)
  10.     lista.append(lista2)
  11.  
  12. x2,y2 = x,y
  13. print x,y,x2,y2
  14. lista2 = []
  15.  
  16. suma = 0
  17. while (x2-1>=0 and y2-1>=0):
  18.     if lista[x2-1][y2-1]==".":
  19.         x2 = x2-1
  20.         y2 = y2-1
  21.         suma = suma+1
  22.     if lista[x2-1][y2-1]=="#":
  23.         break
  24. lista2.append(suma)
  25. x2,y2 = x,y
  26.  
  27. suma = 0
  28. while (x2+1<a and y2+1<a):
  29.     if lista[x2+1][y2+1]==".":
  30.         x2 = x2+1
  31.         y2 = y2+1
  32.         suma = suma+1
  33.     if lista[x2+1][y2+1]=="#":
  34.         break
  35. lista2.append(suma)
  36. x2,y2 = x,y
  37.  
  38. suma = 0
  39. while (x2-1>=0):
  40.     if lista[x2-1][y2]==".":
  41.         x2 = x2-1
  42.         suma = suma+1
  43.     if lista[x2-1][y2]=="#":
  44.         break
  45. lista2.append(suma)
  46. x2,y2 = x,y
  47.  
  48. suma = 0
  49. while (x2+1<a):
  50.     if lista[x2+1][y2]==".":
  51.         x2 = x2+1
  52.         suma = suma+1
  53.     if lista[x2+1][y2]=="#":
  54.         break
  55. lista2.append(suma)
  56. x2,y2 = x,y
  57.  
  58. suma = 0
  59. while (y2-1>=0):
  60.     if lista[x2][y2-1]==".":
  61.         y2 = y2-1
  62.         suma = suma+1
  63.     if lista[x2][y2-1]=="#":
  64.         break
  65. lista2.append(suma)
  66. x2,y2 = x,y
  67.  
  68. suma = 0
  69. while (y2+1<a):
  70.     if lista[x2][y2+1]==".":
  71.         y2 = y2+1
  72.         suma = suma+1
  73.     if lista[x2][y2+1]=="#":
  74.         break
  75. lista2.append(suma)
  76. x2,y2 = x,y
  77.  
  78. suma = 0
  79. while (x2-1>=0 and y2+1<a):
  80.     if lista[x2-1][y2+1]==".":
  81.         x2 = x2-1
  82.         y2 = y2+1
  83.         suma = suma+1
  84.     if lista[x2-1][y2+1]=="#":
  85.         break
  86. lista2.append(suma)
  87. x2,y2 = x,y
  88.  
  89. suma = 0
  90. while (x2+1<a and y2-1>=0):
  91.     if lista[x2+1][y2-1]==".":
  92.         x2 = x2+1
  93.         y2 = y2-1
  94.         suma = suma+1
  95.     if lista[x2+1][y2-1]=="#":
  96.         break
  97. lista2.append(suma)
  98. x2,y2 = x,y
  99.  
  100. menor = 100
  101. for C in lista2:
  102.     if C<menor:
  103.         menor = C
  104.  
  105. print menor

Gracias ;)
__________________
"Porque nada se...
quiero saberlo todo"