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 ;)

[razpeitia]

Código Python:

def searchR(grid):
    for i, row in enumerate(grid):
        for j, value in enumerate(row):
            if value == 'R':
                return (i, j)
 
def searchExit(grid, n, x, y, dx, dy):
    c = 0
    while 0 <= x < n and 0 <= y < n:
        if grid[x][y] == '#':
            return -1
        c += 1
        x += dx
        y += dy
    return c
    
    
n = int(raw_input())
 
grid = []
for i in range(n):
    grid.append(raw_input())
 
x, y = searchR(grid)
 
l = [
    (1, 1),
    (1, 0),
    (0, 1),
    (0, -1),
    (0, -1),
    (-1, 0),
    (-1, 0)
    ]
 
ans = []
for dx, dy in l:
    res = searchExit(grid, n, x, y, dx, dy)
    if res >= 1:
        ans.append(res)
if ans:
    print min(ans) - 1
else:
    print -1
 

La única cosa que tienes que hacer es checar las 8 posibles lineas rectas, ver si se salen del mapa y de ser así guardarlas.

Este problema es mucho mas fácil cuando el robot puede girar