Introducci贸n

1

驴Qu茅 es un grafo?

2

驴Qu茅 es un 谩rbol?

3

驴Qu茅 es recursi贸n?

4

Aplicaciones reales de grafos y 谩rboles

5

Formas de representar un grafo

DFS

6

An谩lisis de DFS: algoritmo de b煤squeda en profundidad

7

Programando DFS de forma recursiva

8

Otras formas de programar DFS

9

Recorridos y profundidad de un 脕rbol

10

Sum Root to Leaf Numbers: an谩lisis del problema

11

Soluci贸n de Sum Root to Leaf Numbers

12

Playground: Sum Root to Leaf Numbers

13

Programando Sum Root to Leaf Numbers en Golang

14

Number of Islands: an谩lisis del problema

15

Soluci贸n de Number of Islands

16

Playground: Number of Islands

17

Programando Number of Islands en Python

18

Ejercicios recomendados de DFS

19

Ejercicios resueltos de DFS

BFS

20

An谩lisis de BFS: algoritmo de b煤squeda en anchura

21

Programando BFS con Python

22

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

23

Soluci贸n de Minimum Knights Moves

24

Playground: Minimum Knights Moves

25

Programando Minimum Knights Moves con Python

26

Rotting Oranges: an谩lisis del problema

27

Soluci贸n de Rotting Oranges

28

Playground: Rotting Oranges

29

Rotting Oranges con Java

30

Shortest Bridge Between Islands: an谩lisis del problema

31

Soluci贸n de Shortest Bridge Between Islands

32

Playground: Shortest Bridge Between Islands

33

Programando Shortest Bridge Between Islands con Python

34

Ejercicios recomendados de BFS

35

Ejercicios resueltos de BFS

Backtrack

36

Algoritmo de Backtrack

37

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

38

Soluci贸n de Letter Combinations of a Phone Number

39

Programando Letter Combinations of a Phone Number con C++

40

Playground: Letter Combinations of a Phone Number

41

Restore IP Addresses: an谩lisis del problema

42

Programando Restore IP Addresses con C++

43

Playground: Restore IP Addresses

44

Word Search: an谩lisis del problema

45

Soluci贸n de Word Search

46

Playgrund: Word Search

47

Programando Word Search JavaScript

48

Reto: N Queens Puzzle

49

Ejercicios recomendados de Backtrack

50

Ejercicios resueltos de Backtrack

Pr贸ximos pasos

51

驴Qu茅 otros algoritmos y tipos de grafos puedes aprender?

52

驴Quieres m谩s cursos avanzados de algoritmos?

You don't have access to this class

Keep learning! Join and start boosting your career

Aprovecha el precio especial y haz tu profesi贸n a prueba de IA

Antes: $249

Currency
$209
Suscr铆bete

Termina en:

2 D铆as
2 Hrs
17 Min
13 Seg

Playground: Minimum Knights Moves

24/52

Contributions 5

Questions 0

Sort by:

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

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

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