0

Dada una cuadrícula de m x n llena de números no negativos, encuentre un camino desde la parte superior izquierda hasta la parte inferior derecha que minimice la suma de todos los números a lo largo de su ruta.

Nota: Solo puede moverse hacia abajo o hacia la derecha en cualquier momento.

Quiero saber como moverse en una lista de listas.

Por ejemplo con:

[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]

Por ejemplo

class gridValued:

    def init(self, grid: List[List[int]]):
        self.grid=grid
        gridRight = new gridValued([grid[i][1:] for i in range(0,len (grid))])
        self.lengthRight = gridRight.value
        gridDown = new gridValued([grid[i][0:] for i in range(1,len (grid))])
1
  • En una lista de listas l, cuando accedes a l[0] verás su primer elemento, que es otra lista, y por tanto l[0][0] te dará el primer elemento de esa sublista. Es decir, de forma general, l[i][j] te permite acceder al elemento j de la fila i.
    – abulafia
    el 4 abr. 2019 a las 9:40

1 respuesta 1

0

En cada posición de la matriz tenemos dos caminos: derecha y abajo. Como excepción estaría la última fila y última columna, que sólo tiene un camino, y el último elemento de la esquina inferior derecha, que no tiene ningún camino.

Imagina que tenemos una función que genera los caminos, desde la posición (i,j) a la posición (n,m):

def caminos(matriz: List[List[int]]) -> List[List[int]]:
    n, m = len(matriz)-1, len(matriz[0])-1

    def aux(i: int, j: int) -> List[List[int]]:

        rutas = [[]] if (i,j) == (n,m) else (       # sin caminos
                  (aux(i+1, j) if i < n else []) +  # caminos abajo
                  (aux(i, j+1) if j < m else [])    # caminos derecha
                )

        return [[matriz[i][j]] + r for r in rutas]

    return aux(0, 0)

Para obtener la ruta mínima:

ruta_minima = min(caminos(matriz), key=sum)

A tener en cuenta que esta sería una solución por fuerza bruta calculando todas las rutas posibles. Hay otras estrategias mejores; pero sirve para dar una idea clar de cómo moverse por la matriz.

0

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.