Programando Shortest Bridge Between Islands con Python

```js from typing import List class Bridge: def shortestBridge(self, map: List[List[int]]) -> int: def dfs(i, j): if 0 <= i < len(map) and 0 <= j < len(map[0]) and map[i][j] == 1: map[i][j] = 2 q.append((i, j)) [dfs(x, y) for x, y in [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]] q = [] i, j = next((i, j) for i in range(len(map)) for j in range(len(map)) if map[i][j]) dfs(i, j) bridge = 0 while q: for _ in range(len(q)): i, j = q.pop(0) for a, b in [[0, 1], [0, -1], [1, 0], [-1, 0]]: if 0 <= i + a < len(map) and 0 <= j + b < len(map): if map[i + a][j + b] == 1: return bridge if map[i + a][j + b] == 0: map[i + a][j + b] = 2 q.append((i + a, j + b)) bridge += 1 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]] Bridge().shortestBridge(map) map = [[1,1,0,0,1], [1,1,0,0,1], [1,0,0,0,1], [1,0,0,0,1], [1,0,0,1,1]] Bridge().shortestBridge(map) ```

```js from typing import List from itertools import pairwise from collections import deque class Bridge: def shortestBridge(self, map: List[List[int]]) -> int: def dfs(i, j): q.append((i, j)) map[i][j] = 2 for a, b in pairwise((-1, 0, 1, 0, -1)): x, y = i + a, j + b if 0 <= x < len(map) and 0 <= y < len(map) and map[x][y] == 1: dfs(x, y) q = deque() i, j = next((i, j) for i in range(len(map)) for j in range(len(map)) if map[i][j]) dfs(i, j) bridge = 0 while 1: for _ in range(len(q)): i, j = q.popleft() for a, b in pairwise((-1, 0, 1, 0, -1)): x, y = i + a, j + b if 0 <= x < len(map) and 0 <= y < len(map): if map[x][y] == 1: return bridge if map[x][y] == 0: map[x][y] = 2 q.append((x, y)) bridge += 1 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 = Bridge().shortestBridge(map) print(response) map = [ [1,1,0,0,1], [1,1,0,0,1], [1,0,0,0,1], [1,0,0,0,1], [1,0,0,1,1], ] response = Bridge().shortestBridge(map) print(response) ```

Desarrollé una solución que, aunque es algo distinta de la presentada en clase, refleja un enfoque creativo y completamente propio, sin ayuda externa. No estoy completamente seguro de si este enfoque aumenta la complejidad temporal, pero he comprobado que resuelve el problema de manera efectiva. Decidí modular el problema dividiéndolo en dos partes: 1. En la primera parte, el código localiza los límites de la primera isla encontrada. 2. En la segunda parte, evalúa los espacios de agua para calcular la distancia mínima posible entre las dos islas. A continuación, presento mi código para que puedas revisarlo y ver si es necesario ajustar algo ```python def shrtestBetweenIsland(matriz): if not matriz: return -1 cola = [(0, 0)] steps = [(+1 , 0) , (-1 , 0) , (0 , +1) , (0 , -1)] extremos = [] lugares = set() limx = len(matriz) limy = len(matriz[0]) distancia = 0 while cola: for _ in range(len(cola)): posicionActual = cola.pop(0) lugares.add(posicionActual) for xd , yd in steps: nextPosicion = (posicionActual[0] + xd , posicionActual[1] + yd) if nextPosicion in lugares: continue if not (0 <= nextPosicion[0] < limx) or not (0 <= nextPosicion[1] < limy): continue if matriz[nextPosicion[0]][nextPosicion[1]] == 1: cola.append(nextPosicion) if matriz[nextPosicion[0]][nextPosicion[1]] == 0: extremos.append(posicionActual) while extremos: for _ in range(len(extremos)): posicionActual = extremos.pop(0) lugares.add(posicionActual) for xd , yd in steps: nextPosicion = (posicionActual[0] + xd , posicionActual[1] + yd) if nextPosicion in lugares: continue if not (0 <= nextPosicion[0] < limx) or not (0 <= nextPosicion[1] < limy): continue if matriz[nextPosicion[0]][nextPosicion[1]] == 1: return distancia extremos.append(nextPosicion) distancia += 1 ```

```js from typing import List class Bridge: def shortestBridge(self, map: List[List[str]]) -> int: def dfs(i, j): if 0 <= i < len(map) and 0 <= j < len(map[0]) and map[i][j] == 1: map[i][j] = 2 queue.append((i, j)) [dfs(x, y) for x, y in [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]] queue = [] islandFound = False # DFS to mark the first island for i in range(len(map)): for j in range(len(map[0])): if islandFound: break if map[i][j] == 1: dfs(i, j) islandFound = True break # BFS to find the shortest bridge bridgeSize = 0 while queue: currentQueue = [] while queue: currentCell = queue.pop(0) for x, y in [[0, 1], [0, -1], [1, 0], [-1, 0]]: newX = x + currentCell[0] newY = y + currentCell[1] if (newX < 0 or newX >= len(map) or newY < 0 or newY >= len(map[newX]) or map[newX][newY] == 2): continue if map[newX][newY] == 1: return bridgeSize currentQueue.append([newX, newY]) map[newX][newY] = 2 queue = currentQueue bridgeSize += 1 return -1 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 = Bridge().shortestBridge(map) print(response) map = [ [1,1,0,0,1], [1,1,0,0,1], [1,0,0,0,1], [1,0,0,0,1], [1,0,0,1,1], ] response = Bridge().shortestBridge(map) print(response) ```