Búsqueda en anchura: Ejercicios prácticos y aplicaciones

Curso de Algoritmos Avanzados: Grafos y Árboles

Contenido del curso

Introducción

DFS

BFS

Backtrack

Próximos pasos

Tomar examen

Ejercicios recomendados de BFS

Buscaminas ¡Juguemos al juego del buscaminas! Se le da un tablero de matriz de m x n caracteres que representa el tablero de juego donde:

'M' representa una mina no revelada,
'E' representa una casilla vacía no revelada,
'B' representa un cuadrado vacío revelado que no tiene minas adyacentes (es decir, arriba, abajo, izquierda, derecha y las 4 diagonales) el dígito ('1' a '8') representa cuántas minas están adyacentes a esta casilla revelada.
'X' representa una mina revelada.

También se le da un array entero click donde click = [clickr, clickc] representa la siguiente posición de click entre todas las casillas no reveladas ('M' o 'E'). Devuelve el tablero después de revelar esta posición de acuerdo con las siguientes reglas:

Si se revela una mina 'M', entonces el juego ha terminado. Debes cambiarla por una 'X'.
Si se revela una casilla vacía "E" sin minas adyacentes, entonces cámbiala por una "B" revelada y todas sus casillas adyacentes no reveladas deben ser reveladas recursivamente.
Si se revela una casilla vacía "E" con al menos una mina adyacente, entonces cámbiala por un dígito ("1" a "8") que represente el número de minas adyacentes.

Devuelve el tablero cuando no se revelen más casillas.

Vuelos más baratos con K paradas Hay n ciudades conectadas por un cierto número de vuelos. Se le da un array flights donde flights[i] = [fromi, toi, pricei] indica que hay un vuelo desde la ciudad fromi a la ciudad toi con un precioi. También se le dan tres enteros src, dst y k, devuelve el precio más barato de src a dst con un máximo de k paradas. Si no existe tal ruta, devuelve -1.

Ejemplo 1: Entrada:

n = 4
vuelos = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]]
src = 0
dst = 3
k = 1 Salida: 700

Explicación:El gráfico se muestra arriba. El camino óptimo, con un máximo de 1 parada, desde la ciudad 0 a la 3 está marcado en rojo y tiene un coste de 100 + 600 = 700. Nótese que el camino que pasa por las ciudades [0,1,2,3] es más barato pero no es válido porque utiliza 2 paradas.

Juego Escalera y Serpientes Se le da un tablero de matriz entera n x n en el que las casillas están etiquetadas de 1 a n2 al estilo Boustrophedon empezando por la parte inferior izquierda del tablero (es decir, tablero[n - 1][0]) y alternando la dirección de cada fila. Se comienza en la casilla 1 del tablero. En cada movimiento, partiendo de la casilla curr, haz lo siguiente Elige una casilla de destino próxima con una etiqueta en el rango [curr + 1, min(curr + 6, n2)]. Esta elección simula el resultado de una tirada estándar de 6 caras: es decir, siempre hay como máximo 6 destinos, independientemente del tamaño del tablero. Si el siguiente tiene una serpiente o escalera, debes moverte al destino de esa serpiente o escalera. En caso contrario, te mueves a siguiente.

El juego termina cuando se llega a la casilla n2. Una casilla del tablero en la fila r y la columna c tiene una serpiente o escalera si tablero[r][c] != -1. El destino de esa serpiente o escalera es el tablero[r][c]. Las casillas 1 y n2 no tienen serpiente o escalera. Ten en cuenta que sólo puedes coger una serpiente o escalera como máximo una vez por movimiento. Si el destino de una serpiente o escalera es el inicio de otra serpiente o escalera, no sigues la siguiente serpiente o escalera. Por ejemplo, suponga que el tablero es [[-1,4],[-1,3]], y en el primer movimiento, su casilla de destino es la 2. Sigue la escalera hasta la casilla 3, pero no sigue la escalera posterior hasta la 4. Devuelve el menor número de movimientos necesarios para llegar a la casilla n2. Si no es posible llegar a la casilla, devuelve -1.

Ejemplo 1: Entrada: board=[[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,35,-1,-1,13,-1],[-1,-1,-1,-1,-1,-1],[-1,15,-1,-1,-1,-1]] Salida: 4

Explicación: Al principio, empiezas en la casilla 1 (en la fila 5, columna 0). Decides moverte a la casilla 2 y debes llevar la escalera hasta la casilla 15. Luego decides moverte a la casilla 17 y debes llevar la serpiente a la casilla 13. Luego decides moverte a la casilla 14 y debes llevar la escalera a la casilla 35. Entonces decides moverte a la casilla 36, terminando el juego. Este es el menor número posible de movimientos para llegar a la última casilla, así que devuelve 4.

Horario del Curso Hay un total de numCursos cursos que tiene que tomar, etiquetados de 0 a numCursos - 1. Se le da una matriz prerrequisitos donde prerrequisitos[i] = [ai, bi] indica que debe tomar el curso bi primero si quiere tomar el curso ai. Por ejemplo, el par [0, 1], indica que para tomar el curso 0 hay que tomar primero el curso 1. Devuelve true si puedes terminar todos los cursos. En caso contrario, devuelve false.

Ejemplo 1: Entrada: numCursos = 2, prerrequisitos = [[1,0]] Salida: true Explicación: Hay un total de 2 cursos para tomar. Para tomar el curso 1 debes haber terminado el curso 0. Así que es posible.

Búsqueda en anchura: Ejercicios prácticos y aplicaciones

while cola:
    fila, columna = cola.popleft()
    
    if tablero[fila][columna] == 'E':
        minas = contarMinas(tablero, fila, columna)

        if minas == 0:
            tablero[fila][columna] = 'B'
            for i in range(fila - 1, fila + 2):
                for j in range(columna - 1, columna + 2):
                    if 0 <= i < len(tablero) and 0 <= j < len(tablero[0]):
                        cola.append((i, j))
                        tablero[i][j] = 'B'  # Marcar como visitado
        else:
            tablero[fila][columna] = str(minas)

def actualizarTablero(tablero, clic):

&#x20;   fila, columna = clic

&#x20;   if tablero\[fila]\[columna] == 'M':

&#x20;       \# Caso 1: Mina revelada, el juego termina

&#x20;       tablero\[fila]\[columna] = 'X'

&#x20;   else:

&#x20;       \# Caso 2: Casilla vacía revelada, utilizar BFS

&#x20;       bfs(tablero, fila, columna)

&#x20;   return tablero

def bfs(tablero, fila\_inicio, columna\_inicio):

&#x20;   cola = deque(\[(fila\_inicio, columna\_inicio)])

&#x20;   while cola:

&#x20;       fila, columna = cola.popleft()

&#x20;      &#x20;

&#x20;       if tablero\[fila]\[columna] == 'E':

&#x20;           minas = contarMinas(tablero, fila, columna)

&#x20;           if minas == 0:

&#x20;               \# Caso 2.1: Casilla vacía sin minas adyacentes

&#x20;               tablero\[fila]\[columna] = 'B'

&#x20;               for i in range(fila - 1, fila + 2):

&#x20;                   for j in range(columna - 1, columna + 2):

&#x20;                       if 0 <= i < len(tablero) and 0 <= j < len(tablero\[0]):

&#x20;                           cola.append((i, j))

&#x20;                           tablero\[i]\[j] = 'B'  # Marcar como visitado

&#x20;           else:

&#x20;               \# Caso 2.2: Casilla vacía con al menos una mina adyacente

&#x20;               tablero\[fila]\[columna] = str(minas)

def contarMinas(tablero, fila, columna):

&#x20;   minas = 0

&#x20;   for i in range(fila - 1, fila + 2):

&#x20;       for j in range(columna - 1, columna + 2):

&#x20;           if 0 <= i < len(tablero) and 0 <= j < len(tablero\[0]) and tablero\[i]\[j] == 'M':

&#x20;               minas += 1

&#x20;   return minas

\# Ejemplo de uso

tablero = \[

&#x20;   \['E', 'E', 'E', 'E', 'E'],

&#x20;   \['E', 'E', 'M', 'E', 'E'],

&#x20;   \['E', 'E', 'E', 'E', 'E'],

&#x20;   \['E', 'E', 'E', 'E', 'E']

]

clic = \[3, 0]

resultado = actualizarTablero(tablero, clic)

for fila in resultado:

&#x20;   print(fila)

while cola:
    fila, columna = cola.popleft()
    
    if tablero[fila][columna] == 'E':
        minas = contarMinas(tablero, fila, columna)

        if minas == 0:
            tablero[fila][columna] = 'B'
            for i in range(fila - 1, fila + 2):
                for j in range(columna - 1, columna + 2):
                    if 0 <= i < len(tablero) and 0 <= j < len(tablero[0]):
                        cola.append((i, j))
                        tablero[i][j] = 'B'  # Marcar como visitado
        else:
            tablero[fila][columna] = str(minas)

def actualizarTablero(tablero, clic):

&#x20;   fila, columna = clic

&#x20;   if tablero\[fila]\[columna] == 'M':

&#x20;       \# Caso 1: Mina revelada, el juego termina

&#x20;       tablero\[fila]\[columna] = 'X'

&#x20;   else:

&#x20;       \# Caso 2: Casilla vacía revelada, utilizar BFS

&#x20;       bfs(tablero, fila, columna)

&#x20;   return tablero

def bfs(tablero, fila\_inicio, columna\_inicio):

&#x20;   cola = deque(\[(fila\_inicio, columna\_inicio)])

&#x20;   while cola:

&#x20;       fila, columna = cola.popleft()

&#x20;      &#x20;

&#x20;       if tablero\[fila]\[columna] == 'E':

&#x20;           minas = contarMinas(tablero, fila, columna)

&#x20;           if minas == 0:

&#x20;               \# Caso 2.1: Casilla vacía sin minas adyacentes

&#x20;               tablero\[fila]\[columna] = 'B'

&#x20;               for i in range(fila - 1, fila + 2):

&#x20;                   for j in range(columna - 1, columna + 2):

&#x20;                       if 0 <= i < len(tablero) and 0 <= j < len(tablero\[0]):

&#x20;                           cola.append((i, j))

&#x20;                           tablero\[i]\[j] = 'B'  # Marcar como visitado

&#x20;           else:

&#x20;               \# Caso 2.2: Casilla vacía con al menos una mina adyacente

&#x20;               tablero\[fila]\[columna] = str(minas)

def contarMinas(tablero, fila, columna):

&#x20;   minas = 0

&#x20;   for i in range(fila - 1, fila + 2):

&#x20;       for j in range(columna - 1, columna + 2):

&#x20;           if 0 <= i < len(tablero) and 0 <= j < len(tablero\[0]) and tablero\[i]\[j] == 'M':

&#x20;               minas += 1

&#x20;   return minas

\# Ejemplo de uso

tablero = \[

&#x20;   \['E', 'E', 'E', 'E', 'E'],

&#x20;   \['E', 'E', 'M', 'E', 'E'],

&#x20;   \['E', 'E', 'E', 'E', 'E'],

&#x20;   \['E', 'E', 'E', 'E', 'E']

]

clic = \[3, 0]

resultado = actualizarTablero(tablero, clic)

for fila in resultado:

&#x20;   print(fila)

Búsqueda en anchura: Ejercicios prácticos y aplicaciones

Introducción

Qué son los grafos y cómo modelan el mundo

Qué es un árbol en estructuras de datos

Qué es la recursión en programación

Grafos en el mundo real que ya conoces

Representación de Grafos: Matriz y Lista de Adyacencia

DFS

Cómo recorre nodos el algoritmo DFS

Implementación de DFS recursivo para búsqueda en árboles

Búsqueda en Profundidad (DFS) para Grafos: Enfoque Iterativo y Recursivo

Inorder, Preorder y Postorder en árboles

Suma de caminos raíz a hoja en árboles

Suma de caminos raíz a hoja con DFS

Playground: Sum Root to Leaf Numbers

Implementación de Algoritmo DFS en Árboles Binarios con Golang

Número de islas con DFS en matrices

Problema de islas resuelto con DFS

Playground: Number of Islands

Número de islas con DFS recursivo en Python

Ejercicios Prácticos de Búsqueda en Profundidad (DFS)

Algoritmos de Búsqueda en Profundidad (DFS) en Problemas Comunes

BFS

Cómo BFS recorre grafos por niveles

Implementación de BFS con colas en Python

Mínimos movimientos del caballo en ajedrez

Minimum Knight's Move con BFS

Playground: Minimum Knights Moves

Resolución de Problemas de Caballos de Ajedrez con BFS en Python

Propagación BFS en Rotting Oranges

Resolución de Rotting Oranges usando BFS

Playground: Rotting Oranges

Implementación de BFS para naranjas podridas

Puente más corto entre islas con BFS

Shortest Bridge: combina DFS y BFS

Playground: Shortest Bridge Between Islands

Shortest Bridge con DFS y BFS en Python