fork download 
  1. def esValido(n, m, i, j, lab):
  2.     return 0 <= i < m and 0 <= j < n and lab[i][j] == 0
  3.  
  4. def recorroLab(lab):
  5.     m, n = len(lab), len(lab[0])
  6.     min_path = [float('inf')]  # Almacenará la longitud mínima del camino
  7.     best_path = [None]  # Almacenará el mejor camino encontrado
  8.  
  9.     def recorrido(i, j, path):
  10.         if not esValido(n, m, i, j, lab):
  11.             return
  12.  
  13.         if (i, j) == (m - 1, n - 1):  # Si hemos llegado al final
  14.             if len(path) < min_path[0]:  # Si el nuevo camino es más corto
  15.                 min_path[0] = len(path)  # Actualizamos la longitud mínima
  16.                 best_path[0] = path  # Actualizamos el mejor camino
  17.             return
  18.  
  19.         lab[i][j] = 1  # Marcamos la celda como visitada
  20.  
  21.         # Exploramos los cuatro posibles movimientos: arriba, abajo, izquierda, derecha
  22.         recorrido(i + 1, j, path + "D")
  23.         recorrido(i - 1, j, path + "U")
  24.         recorrido(i, j + 1, path + "R")
  25.         recorrido(i, j - 1, path + "L")
  26.  
  27.         lab[i][j] = 0  # Desmarcamos la celda para futuras exploraciones
  28.  
  29.     # Comenzamos la exploración desde la posición inicial (0, 0) con un camino vacío
  30.     recorrido(0, 0, "")
  31.  
  32.     return best_path[0]  # Devolvemos el mejor camino encontrado
  33.  
  34. laberinto = [
  35.     [0, 0, 1, 0, 0],
  36.     [1, 0, 1, 0, 1],
  37.     [1, 0, 0, 0, 1],
  38.     [1, 0, 0, 0, 0],
  39.     [0, 1, 0, 1, 0]
  40. ]
  41.  
  42. print(recorroLab(laberinto))
  43.  
Success #stdin #stdout 0.03s 9564KB
comments (?)
stdin 
Standard input is empty
stdout 
RDDDRRRD
https://ideone.com/Nns60G
language:
Python 3 (python  3.9.5)
created:
16 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!