Playground: Minimum Knights Moves

Curso de Algoritmos Avanzados: Grafos y Árboles

Introducción

¿Qué es un grafo?

¿Qué es un árbol?

¿Qué es recursión?

Aplicaciones reales de grafos y árboles

Formas de representar un grafo

DFS

Análisis de DFS: algoritmo de búsqueda en profundidad

Programando DFS de forma recursiva

Otras formas de programar DFS

Recorridos y profundidad de un Árbol

Sum Root to Leaf Numbers: análisis del problema

Solución de Sum Root to Leaf Numbers

Playground: Sum Root to Leaf Numbers

Programando Sum Root to Leaf Numbers en Golang

Number of Islands: análisis del problema

Solución de Number of Islands

Playground: Number of Islands

Programando Number of Islands en Python

Ejercicios recomendados de DFS

Ejercicios resueltos de DFS

BFS

Análisis de BFS: algoritmo de búsqueda en anchura

Programando BFS con Python

Minimum Knights Moves (movimientos de caballo en ajedrez): análisis del problema

Solución de Minimum Knights Moves

Playground: Minimum Knights Moves

Programando Minimum Knights Moves con Python

Rotting Oranges: análisis del problema

Solución de Rotting Oranges

Playground: Rotting Oranges

Rotting Oranges con Java

Shortest Bridge Between Islands: análisis del problema

Solución de Shortest Bridge Between Islands

Playground: Shortest Bridge Between Islands

Programando Shortest Bridge Between Islands con Python

Ejercicios recomendados de BFS

Ejercicios resueltos de BFS

Backtrack

Algoritmo de Backtrack

Letter Combinations of a Phone Number: análisis del problema

Solución de Letter Combinations of a Phone Number

Programando Letter Combinations of a Phone Number con C++

Playground: Letter Combinations of a Phone Number

Restore IP Addresses: análisis del problema

Programando Restore IP Addresses con C++

Playground: Restore IP Addresses

Word Search: análisis del problema

Solución de Word Search

Playgrund: Word Search

Programando Word Search JavaScript

Reto: N Queens Puzzle

Ejercicios recomendados de Backtrack

Ejercicios resueltos de Backtrack

Próximos pasos

¿Qué otros algoritmos y tipos de grafos puedes aprender?

¿Quieres más cursos avanzados de algoritmos?

No tienes acceso a esta clase

¡Continúa aprendiendo! Únete y comienza a potenciar tu carrera

Si ya tienes una cuenta,

Aportes 3

Preguntas 0

Ordenar por:

¿Quieres ver más aportes, preguntas y respuestas de la comunidad?

Jose Miguel Murillo Cediel

hace 9 meses

```python from collections import deque def minKnightMoves(origenX, origenY, objetivoX, objetivoY): # Posibles movimientos del caballo en el tablero movimientos = [(1, 2), (1, -2), (-1, 2), (-1, -2), (2, 1), (2, -1), (-2, 1), (-2, -1)] # BFS cola = deque([(origenX, origenY, 0)]) visitado = set() while cola: x, y, pasos = cola.popleft() if x == objetivoX and y == objetivoY: return pasos for dx, dy in movimientos: nuevo_x, nuevo_y = x + dx, y + dy if (nuevo_x, nuevo_y) not in visitado: visitado.add((nuevo_x, nuevo_y)) cola.append((nuevo_x, nuevo_y, pasos + 1)) return -1 ```

Jose Miguel Murillo Cediel

hace 9 meses

Para probar con este from collections import dequedef minKnightMoves(origenX, origenY, objetivoX, objetivoY): # Posibles movimientos del caballo en el tablero movimientos = \[(1, 2), (1, -2), (-1, 2), (-1, -2), (2, 1), (2, -1), (-2, 1), (-2, -1)] # BFS cola = deque(\[(origenX, origenY, 0)]) visitado = set() while cola: x, y, pasos = cola.popleft() if x == objetivoX and y == objetivoY: return pasos for dx, dy in movimientos: nuevo\_x, nuevo\_y = x + dx, y + dy if (nuevo\_x, nuevo\_y) not in visitado: visitado.add((nuevo\_x, nuevo\_y)) cola.append((nuevo\_x, nuevo\_y, pasos + 1)) return -1

Ivan Scaglioni

hace un año

Mi solución no pasa el segundo test, pero a mí me funciona bien.

Este código filtra algunos movimientos, lo que lo hace más eficiente.

PD: Vengo desde la próxima clase y me faltó poner una forma de verificar si ya había visitado un lugar en el tablero.

def minKnightMoves(origenX, origenY, objetivoX, objetivoY):
   # Tu código aquí 👇
    saltos = 0
    movimientos = [(origenX,origenY)]
    while movimientos:
        for _ in range(len(movimientos)):
            mov = movimientos.pop(0)
            x = mov[0]
            y = mov[1]
            current_modulo = int(((x - objetivoX )**2 + (y - objetivoY)**2)**(1/2)) 
            print(current_modulo)
            if x == objetivoX and y == objetivoY:
                print("-------------------")
                print(x,y)
                print("-------------------")
                return saltos 
            for next_mov in [(-1,2),(1,2),(2,1),(2,-1),(1,-2),(-1,-2),(-2,1),(-2,-1)]:
                """mi pequeño aporte para mejorar un poco el rendimineto"""
                new_modulo = int((((x + next_mov[0] )- objetivoX )**2 + ((y + next_mov[1]) - objetivoY)**2)**(1/2))
                if current_modulo-1 > new_modulo or new_modulo <= 2:
                    movimientos.append((x + next_mov[0] , y + next_mov[1] ))  

        saltos += 1


    return saltos```