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?

You don't have access to this class

Keep learning! Join and start boosting your career

If you already have an account,

Contributions 5

Questions 0

Sort by:

Want to see more contributions, questions and answers from the community?

Cristian Toro

6 months ago

Esta es mi solución. Inicialmente, había implementado un enfoque diferente, pero ajusté el código para cumplir con los requisitos del desafío y asegurar que pasara todas las pruebas. ```js def minKnightMoves(origenX, origenY, objetivoX, objetivoY): origen = (origenX , origenY) objetivo = (objetivoX , objetivoY) if origen == objetivo: return [] movimientos = [] cola = [origen] lugares = [] niveles = 1 direcciones = [(-1 ,2), (1 ,2), (-1, -2), (1, -2), (2, -1), (2, 1), (-2, -1), (-2, 1)] while cola: for _ in range(len(cola)): posicionActual = cola.pop(0) if posicionActual == objetivo: movimientos.append(posicionActual) return niveles lugares.append(posicionActual) for xd , yd in direcciones: nextPosicion = posicionActual[0] + xd , posicionActual[1] + yd if nextPosicion in lugares: continue if nextPosicion == objetivo: movimientos.append(nextPosicion) return niveles cola.append(nextPosicion) niveles += 1 if niveles > 8: print("no se encontro objetivo en 8 pasos") return [] return niveles ```

Carlos Hernandez

3 months ago

Mi solución: ```python def generate_possible_moves(x, y): # Generate clockwise positions return [(x+1, y+2), (x+2, y+1), (x+2, y-1), (x+1, y-2), (x-1, y-2), (x-2, y-1), (x-2, y+1), (x-1, y+2)] def minKnightMoves(originX, originY, targetX, targetY): current_postion = (originX, originY) if current_postion == (targetX, targetY): return 0 queue = [current_postion] moves = 0 while queue: for _ in range(len(queue)): current_postion = queue.pop(0) x, y = current_postion possible_moves = generate_possible_moves(x, y) for move in possible_moves: queue.append(move) moves += 1 if (targetX, targetY) in queue: break return moves print(minKnightMoves(0, 0, 5, 5)) print(minKnightMoves(0, 0, 1, 2)) print(minKnightMoves(0, 0, 0, 0)) print(minKnightMoves(0, 0, 3, 3)) print(minKnightMoves(0, 0, 2, 2)) ```

Jose Miguel Murillo Cediel

a year ago

```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

a year ago

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

2 years ago

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```