Ejercicios avanzados de búsqueda en anchura (BFS) en programación
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.
classSolution: def updateBoard(self,tablero:List[List[str]],click:List[int])->List[List[str]]: numeros ="B123456789" queue =deque([click]) directions =[(-1,0),(1,0),(0,-1),(0,1),(1,1),(-1,-1),(1,-1),(-1,1)]whilequeue: i, j = queue.popleft()if tablero[i][j]=="B":continueif tablero[i][j]=="M": tablero[i][j]="X"break contadorMinasAdyacentes =0 casillasAdyacentes =[] #only used if not adjacent mines
for x, y indirections: x, y = i + x, j + y
if0<= x <len(tablero) and 0<= y <len(tablero[0]) and tablero[x][y]in["M","E"]:if tablero[x][y]=="M": contadorMinasAdyacentes +=1else: casillasAdyacentes.append((x, y))if contadorMinasAdyacentes ==0: queue.extend(casillasAdyacentes) tablero[i][j]= numeros[contadorMinasAdyacentes]return tablero
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.
def findCheapestPrice(self,n: int,flights:List[List[int]],src: int,dst: int,K: int)-> int: graph =defaultdict(list) res =float('inf') cola =[(src,0,0)]for vuelo inflights: graph[vuelo[0]].append((vuelo[1], vuelo[2]))whilecola: viajeActual, nivel, precioActual = cola.pop(0)if nivel >K+1:breakif viajeActual == dst: res =min(res, precioActual)for siguienteVuelo, precioSiguienteVuelo in graph[viajeActual]:if precioSiguienteVuelo + precioActual >= res:continue cola.append((siguienteVuelo, nivel +1, precioSiguienteVuelo + precioActual))if res !=float('inf'):return res
else:return-1
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.
def snakesAndLadders(self, tablero): tablero.reverse() tableroPlano =[0]for i, fila inenumerate(tablero):if i %2==0: tableroPlano += fila
else: tableroPlano += fila[::-1] cola =[1] casillasVisitadas =set() movimientos =0whilecola: siguienteNivel =[]whilecola: casilla = cola.pop()if casilla ==len(tableroPlano)-1:return movimientos
for i inrange(1,7):if casilla + i <=len(tableroPlano)-1 and casilla + i not incasillasVisitadas: casillasVisitadas.add(casilla + i)if tableroPlano[casilla + i]!=-1: siguienteNivel.append(tableroPlano[casilla + i])else: siguienteNivel.append(casilla + i) cola = siguienteNivel
movimientos = movimientos +1return-1
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.
