Clase 32 de 52 • Curso de Algoritmos Avanzados: Grafos y Árboles
Contenido del curso
John Eduard Meneses González
Carlos Hernandez
Miguel Angel Reyes Moreno
My Slution!!
Mi solución:
import math def check_spot(islands, i, j): for index, islands_spots in islands.items(): if (i - 1, j) in islands_spots or (i, j-1) in islands_spots or (i + 1, j) in islands_spots or (i, j + 1) in islands_spots: return index return -1 def get_islands(input_map): islands = {} for i, row in enumerate(input_map): for j, column in enumerate(row): if column == "0": continue else: # Check contiguous spots found_index = check_spot(islands, i, j) # Clock-wise order starting from left if found_index == -1: next_index = len(islands.items()) islands[next_index] = [(i, j)] else: islands[found_index].append((i, j)) return islands def generate_next_steps(islands, i, j, destination): next_steps = [] if (i - 1) >= 0 and islands[i-1][j] == "0" or (i-1,j) == destination: next_steps.append((i-1, j)) if (j + 1) < len(islands[i]) and islands[i][j+1] == "0" or (i,j+1) == destination: next_steps.append((i, j+1)) if (i + 1) < len(islands) and islands[i+1][j] == "0" or (i+1,j) == destination: next_steps.append((i+1, j)) if (j - 1) >= 0 and islands[i][j-1] == "0" or (i,j-1) == destination: next_steps.append((i, j-1)) return next_steps def get_shortest_bridge_between_islands(input_map): islands = get_islands(input_map) shortest_path_data = { "spot_1" : None, "spot_2" : None, "distance": 1000000 } for i1, j1 in islands[0]: for i2, j2 in islands[1]: spots_distance = math.dist([i1, j1], [i2, j2]) if spots_distance < shortest_path_data["distance"]: shortest_path_data['spot_1'] = (i1, j1) shortest_path_data['spot_2'] = (i2, j2) shortest_path_data['distance'] = spots_distance origin, destination = shortest_path_data["spot_1"], shortest_path_data["spot_2"] print(origin, destination) bridge_amount = -1 steps = [origin] while steps: if destination in steps: break for _ in range(len(steps)): current_step = steps.pop(0) i, j = current_step next_steps = generate_next_steps(input_map, i, j, destination) for next_step in next_steps: if not next_step in steps: steps.append(next_step) bridge_amount += 1 print(steps) return bridge_amount input_map = [ ["1","1","1","1","1"], ["1","0","0","0","1"], ["1","0","1","0","1"], ["1","0","0","0","1"], ["1","1","1","1","1"], ] response = get_shortest_bridge_between_islands(input_map) print(response)
comparto una solución con algunos comentarios:
from typing import List from collections import deque class Solution:   def shortestBridge(self, grid: List\[List\[int]]) -> int:   \# Step 1: Find the first island and mark it, adding boundary cells to the queue   found = False   queue = deque() # Boundary of the first island for expansion   for i in range(len(grid)):   for j in range(len(grid\[i])):   if grid\[i]\[j] == 1:   self.mark\_first\_island(grid, i, j, queue) # Mark first island and add boundaries to queue   found = True   break   if found:   break   \# Step 2: Expand BFS from the first island to reach the second island   return self.expand(grid, queue)   def mark\_first\_island(self, grid: List\[List\[int]], x: int, y: int, queue: deque):   directions = \[(1, 0), (-1, 0), (0, 1), (0, -1)]   grid\[x]\[y] = 2 # Mark the island as visited   queue\_for\_marking = deque(\[(x, y)])   while queue\_for\_marking:   x, y = queue\_for\_marking.popleft()   for direction in directions:   new\_x, new\_y = x + direction\[0], y + direction\[1]   if 0 <= new\_x < len(grid) and 0 <= new\_y < len(grid\[0]):   if grid\[new\_x]\[new\_y] == 1:   grid\[new\_x]\[new\_y] = 2 # Mark connected land   queue\_for\_marking.append((new\_x, new\_y))   elif grid\[new\_x]\[new\_y] == 0:   \# Add boundary water cells to queue for BFS expansion   queue.append((x, y))   def expand(self, grid: List\[List\[int]], queue: deque) -> int:   directions = \[(1, 0), (-1, 0), (0, 1), (0, -1)]   steps = 0   \# Start BFS to expand towards the second island   while queue:   for \_ in range(len(queue)):   x, y = queue.popleft()   for direction in directions:   new\_x, new\_y = x + direction\[0], y + direction\[1]   if 0 <= new\_x < len(grid) and 0 <= new\_y < len(grid\[0]):   if grid\[new\_x]\[new\_y] == 1: # Found the second island   return steps   if grid\[new\_x]\[new\_y] == 0: # Expand to water, turn it into land   grid\[new\_x]\[new\_y] = 2   queue.append((new\_x, new\_y))   steps += 1 # Increase the step count as we expand one layer outwards   return -1 # Should never reach here if there are two islands
