Yojan Antonio Pardo Zabala
Mario Alberto Hernández Pintor
Manuel Juarez
esta es mi solución en java, primero obtengo las coordenadas de la primera isla con DFS y luego desde cada punto de la primera isla hago BFS para encontrar la distancia entre las islas
package dev.yojanpardo.grafosarboles.shortestbridge; import dev.yojanpardo.grafosarboles.recursion.Point; import java.util.HashSet; import java.util.LinkedList; import java.util.Queue; import java.util.Set; public class ShortestBridgeBetweenIslands { private static final Point[] DIRECTIONS = new Point[] { new Point(1,0), new Point(0,1), new Point(-1,0), new Point(0,-1) }; public static void main(String[] args) { final int[][] islandsMap = buildIslandsMap(); final Queue<Point> firstIslandCoordinates = findFirstIslandEdges(islandsMap); System.out.printf("the minimum required materials for build a bridge are: [%d]\n", calculateMinimumMaterialsForBridge(islandsMap, firstIslandCoordinates)); } private static int calculateMinimumMaterialsForBridge(int[][] islandsMap, Queue<Point> firstIslandCoordinates) { int minRequiredMaterials = -1; final Set<Point> visitedPoints = new HashSet<>(); while(!firstIslandCoordinates.isEmpty()){ int size = firstIslandCoordinates.size(); for(int i = 0; i < size; i++) { Point islandCoordinate = firstIslandCoordinates.poll(); if(islandCoordinate != null && islandsMap[islandCoordinate.getX()][islandCoordinate.getY()] == 1){ return minRequiredMaterials; } if(!visitedPoints.contains(islandCoordinate)){ visitedPoints.add(islandCoordinate); firstIslandCoordinates.addAll(getPossibleRoutesFromPoint(islandCoordinate, islandsMap)); } } minRequiredMaterials++; } return -1; } private static Queue<Point> getPossibleRoutesFromPoint(Point islandCoordinate, int[][] islandsMap) { final Queue<Point> possibleRoutes = new LinkedList<>(); for(Point direction : DIRECTIONS){ Point point = new Point(islandCoordinate.getX() + direction.getX(), islandCoordinate.getY() + direction.getY()); if(point.getX() >= 0 && point.getY() >= 0 && point.getX() < islandsMap.length && point.getY() < islandsMap[point.getX()].length ){ possibleRoutes.add(point); } } return possibleRoutes; } private static Queue<Point> findFirstIslandEdges(int[][] islandsMap) { final Queue<Point> edgePoints = new LinkedList<>(); for (int x = 0; x < islandsMap.length; x++){ for(int y = 0; y < islandsMap[x].length; y++){ if(islandsMap[x][y] == 1) { dfs(islandsMap, x, y, edgePoints); return edgePoints; } } } return edgePoints; } private static void dfs(int[][] islandsMap, int x, int y, final Queue<Point> edgePoints) { if(x < 0 || y < 0 || x >= islandsMap.length || y >= islandsMap[x].length || islandsMap[x][y] == 0){ return; } islandsMap[x][y] = 0; edgePoints.add(new Point(x,y)); for (Point direction : DIRECTIONS){ dfs(islandsMap, x + direction.getX(), y + direction.getY(), edgePoints); } } /** * builds the map with two islands * @return the array with the islands */ private static int[][] buildIslandsMap() { return new int[][] { {0,1,0,0,0,0,0}, {1,1,1,0,0,0,0}, {0,0,0,0,0,0,0}, {0,0,0,0,0,1,1}, {0,0,0,0,0,1,1}, }; } }
Hice una primera solución usando la distancia Manhatan, ya que solo nos pedían la distancia mas corta:
const mapa1 = [ [1,1,0,0,0], [1,1,0,0,0], [0,0,0,0,0], [0,0,0,1,1]]; const mapa2 = [ [1,1,0,0,0], [1,1,0,0,0], [0,0,1,0,0], [0,0,0,1,1], [1,0,0,1,1]]; const mapa3 = [ [1,1,0,0,0], [1,0,0,0,0], [0,0,1,0,0], [0,0,0,0,1], [0,0,0,1,1]]; const mapa4 = [ [1,0,0,1], [1,0,0,0] ] var DIMS = (mapa=>{ return [mapa.length, mapa[0].length]; })(mapa1); const visitados = []; for (var j = 0;j<DIMS[0];j++){ visitados.push([]); for (var i = 0; i< DIMS[1];i++){ visitados[j].push(false); }}; function obtener_adyacentes(celda) { var adyacentes = []; const direcciones = [ [0,1],[0,-1],[1,0],[-1,0] ]; for (const [r,c] of direcciones){ const nr = celda[0]+r; const nc = celda[1]+c; if (nr >= 0 && nr< DIMS[0] && nc >=0 && nc < DIMS[1]){ if (!visitados[nr][nc]){ adyacentes.push([nr,nc]); }} }; return adyacentes; } function identificarIsla(inicio,mapa) { var isla = [inicio]; var pila = [inicio] while (pila.length > 0){ var celda_actual = pila.pop(); var adyacentes = obtener_adyacentes(celda_actual); if (adyacentes || adyacentes.length > 0){ for (const adj of adyacentes){ if (mapa[adj[0]][adj[1]]){ pila.push(adj) isla.push(adj) } }} visitados[celda_actual[0]][celda_actual[1]] = true; } return isla; } function Manhatan(p1,p2) { return Math.abs(p1[0] - p2[0])+ Math.abs(p1[1]-p2[1]); } function Puente(mapa){ var lasIslas = []; var i,j; for (i = 0; i < DIMS[0];i++){ for (j=0;j< DIMS[1]; j++){ if(mapa[i][j] && !visitados[i][j]){ lasIslas.push(identificarIsla([i,j],mapa)) } } } //console.log(lasIslas.length) var distancia = Infinity for (j = 0;j < lasIslas[0].length; j++){ for (i=0;i< lasIslas[1].length;i++){ var temp = Manhatan(lasIslas[0][j],lasIslas[1][i]); if (distancia > temp){ distancia = temp; } } } console.log("Distancia: ",distancia - 1) return distancia; } //console.log("Manhatan: ", Manhatan([0,0],[0,3])) Puente(mapa1); console.log(visitados)
Acá les dejo mi solución al problema. Apunté a crear una solución general que admite cualquier número de islas, calcula todos los puentes posibles entre ellas y selecciona los de menor longitud. Tiene complejidad O(n²) y todavía hay mucho lugar para optimización, pero funciona bien para matrices menores a 10x10. El código:
import random import collections import itertools def main(): """ Generates a random map of land and water, identifies islands, and finds the shortest bridges between them. The algorithm works as follows: 1. Generates a 2D grid(map) with random land(1) and water(0) cells, based on given weights. 2. Prints the original map for visualization. 3. Uses Depth-First Search(DFS) to traverse the map and mark each island with a unique identifier(marker > 1). - This allows distinguishing between different islands. 4. Counts the number of islands found. 5. For each pair of islands, attempts to build all possible bridges(sequence of water cells) connecting them: - For each cell in an island, performs a Breadth-First Search(BFS) to explore possible bridges to other islands. - Keeps track of the shortest bridge found between each pair of islands. 6. Prints the shortest bridge(if any) between each pair of islands, including its length. 7. Prints the final map with islands marked by unique numbers. """ def generate_land_map(row_number, column_number, land_weight, water_weight): return [[random.choices([0, 1], weights=[water_weight, land_weight])[0] for _ in range(column_number)] for _ in range(row_number)] def format_map(land_map): return [[str(block) if block > 0 else ' ' for block in row] for row in land_map] def print_map(land_map): formated_map = format_map(land_map) for i in range(row_number): print(' '.join(formated_map[i])) def dfs(i, j, islands_marker): if 0 <= i < row_number and 0 <= j < column_number and land_map[i][j] == 1: land_map[i][j] = islands_marker dfs(i+1, j, islands_marker) dfs(i-1, j, islands_marker) dfs(i, j+1, islands_marker) dfs(i, j-1, islands_marker) def measure_island_extension(land_map, marker): return [(i, j) for i in range(len(land_map)) for j in range(len(land_map[0])) if land_map[i][j] == marker] def locate_islands_coordinates(land_map): island_extensions = [] for k in range(number_of_islands): island_extension = measure_island_extension( land_map=land_map, marker=k+2) island_extensions.append(island_extension) return island_extensions def build_bridges(land_map: list[list[int]]): islands = locate_islands_coordinates(land_map=land_map) bridges = [] queue = collections.deque() for island_index in range(len(islands)): island = islands[island_index] a, b = island[0] origin_island = land_map[a][b] for x, y in island: queue.append((x, y, [])) while queue: i, j, bridge = queue.popleft() # Define directions: down, up, right, left directions = [(1, 0), (-1, 0), (0, 1), (0, -1)] for di, dj in directions: ni, nj = i + di, j + dj # Check bounds, water cell, and not already in bridge if (0 <= ni < len(land_map) and 0 <= nj < len(land_map[0]) and land_map[ni][nj] == 0 and (ni, nj) not in bridge): # Create new bridge list new_bridge = bridge + [(ni, nj)] queue.append((ni, nj, new_bridge)) # Check bounds, water cell, and not already in bridge and different island than origin island elif (0 <= ni < len(land_map) and 0 <= nj < len(land_map[0]) and land_map[ni][nj] != 0 and (ni, nj) not in bridge and land_map[ni][nj] != origin_island): destination_island = land_map[ni][nj] bridges.append( (bridge, origin_island, destination_island)) combs = [(i, j) for i, j in itertools.combinations( range(2, len(islands)+2), 2)] for comb in combs: a_to_b_bridges = [ bridge[0] for bridge in bridges if bridge[1] == comb[0] and bridge[2] == comb[1]] shortest_bridge = min( a_to_b_bridges, key=len) if a_to_b_bridges else [] print( f"Shortest bridge from {comb[0]} to {comb[1]}: {shortest_bridge} (Length: {len(shortest_bridge)})" if len(shortest_bridge) else f"No bridge from {comb[0]} to {comb[1]}") row_number = 10 column_number = 10 land_weight = 0.5 water_weight = 0.5 land_map = generate_land_map( row_number, column_number,land_weight,water_weight) number_of_islands = 0 print("\n", "Original map".center(column_number, "*")) print_map(land_map) """ islands_marker marks the different island with different numbers, so the coordinates of the islands can be identified later on """ islands_marker = 1 for i in range(row_number): for j in range(column_number): if land_map[i][j] == 1: islands_marker += 1 dfs(i, j, islands_marker,) number_of_islands += 1 print(f"Number of Islands: {number_of_islands}") build_bridges(land_map) print("\n", "Final map".center(column_number, "*")) print_map(land_map) if __name__ == '__main__': main()
