Ejercicio

[AlanFC]

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.

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:

a = input ()
lista = []
for A in range (a):
    lista2 = []
    b = raw_input ()
    for B in range(a):
        lista2.append(b[B])
        if b[B]=="R":
            y,x = (A,B)
    lista.append(lista2)
 
x2,y2 = x,y
print x,y,x2,y2
lista2 = []
 
suma = 0
while (x2-1>=0 and y2-1>=0):
    if lista[x2-1][y2-1]==".":
        x2 = x2-1
        y2 = y2-1
        suma = suma+1
    if lista[x2-1][y2-1]=="#":
        break
lista2.append(suma)
x2,y2 = x,y
 
suma = 0
while (x2+1<a and y2+1<a):
    if lista[x2+1][y2+1]==".":
        x2 = x2+1
        y2 = y2+1
        suma = suma+1
    if lista[x2+1][y2+1]=="#":
        break
lista2.append(suma)
x2,y2 = x,y
 
suma = 0
while (x2-1>=0):
    if lista[x2-1][y2]==".":
        x2 = x2-1
        suma = suma+1
    if lista[x2-1][y2]=="#":
        break
lista2.append(suma)
x2,y2 = x,y
 
suma = 0
while (x2+1<a):
    if lista[x2+1][y2]==".":
        x2 = x2+1
        suma = suma+1
    if lista[x2+1][y2]=="#":
        break
lista2.append(suma)
x2,y2 = x,y
 
suma = 0
while (y2-1>=0):
    if lista[x2][y2-1]==".":
        y2 = y2-1
        suma = suma+1
    if lista[x2][y2-1]=="#":
        break
lista2.append(suma)
x2,y2 = x,y
 
suma = 0
while (y2+1<a):
    if lista[x2][y2+1]==".":
        y2 = y2+1
        suma = suma+1
    if lista[x2][y2+1]=="#":
        break
lista2.append(suma)
x2,y2 = x,y
 
suma = 0
while (x2-1>=0 and y2+1<a):
    if lista[x2-1][y2+1]==".":
        x2 = x2-1
        y2 = y2+1
        suma = suma+1
    if lista[x2-1][y2+1]=="#":
        break
lista2.append(suma)
x2,y2 = x,y
 
suma = 0
while (x2+1<a and y2-1>=0):
    if lista[x2+1][y2-1]==".":
        x2 = x2+1
        y2 = y2-1
        suma = suma+1
    if lista[x2+1][y2-1]=="#":
        break
lista2.append(suma)
x2,y2 = x,y
 
menor = 100
for C in lista2:
    if C<menor:
        menor = C
 
print menor
 

Gracias ;)