Dada una array booleana 2D. La tarea es encontrar el número de islas distintas donde un grupo de 1 conectados (horizontal o verticalmente) forma una isla. Se considera que dos islas son distintas si y solo si una isla es igual a otra (no rotada ni reflejada).
Ejemplos:
Entrada: rejilla[][] =
{{1, 1, 0, 0, 0},
1, 1, 0, 0, 0},
0, 0, 0, 1, 1},
0, 0, 0, 1 , 1}}
Salida: 1
Isla 1, 1 en la esquina superior izquierda es igual a la isla 1, 1 en la esquina inferior derecha
Entrada: grid[][] =
{{1, 1, 0, 1, 1},
1 , 0, 0, 0, 0},
0, 0, 0, 0, 1},
1, 1, 0, 1, 1}}
Salida: 3
Islas distintas en el ejemplo anterior son: 1, 1 en la parte superior izquierda esquina; 1, 1 en la esquina superior derecha y 1 en la esquina inferior derecha. Ignoramos la isla 1, 1 en la esquina inferior izquierda ya que 1, 1 es idéntica a la esquina superior derecha.
Enfoque: Este problema es una extensión del problema Número de islas .
El núcleo de la pregunta es saber si 2 islas son iguales. El criterio principal es que el número de 1 debe ser el mismo en ambos. Pero este no puede ser el único criterio como hemos visto en el ejemplo 2 anterior. Entonces, ¿cómo sabemos? Podríamos usar la posición/coordenadas de los 1.
Si tomamos las primeras coordenadas de cualquier isla como punto base y luego calculamos las coordenadas de otros puntos desde el punto base, podemos eliminar los duplicados para obtener el recuento distinto de islas. Entonces, usando este enfoque, las coordenadas de las 2 islas en el ejemplo 1 anterior se pueden representar como: [(0, 0), (0, 1), (1, 0), (1, 1)].
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of above approach #include <bits/stdc++.h> using namespace std; // 2D array for the storing the horizontal and vertical // directions. (Up, left, down, right} vector<vector<int> > dirs = { { 0, -1 }, { -1, 0 }, { 0, 1 }, { 1, 0 } }; // Function to perform dfs of the input grid void dfs(vector<vector<int> >& grid, int x0, int y0, int i, int j, vector<pair<int, int> >& v) { int rows = grid.size(), cols = grid[0].size(); if (i < 0 || i >= rows || j < 0 || j >= cols || grid[i][j] <= 0) return; // marking the visited element as -1 grid[i][j] *= -1; // computing coordinates with x0, y0 as base v.push_back({ i - x0, j - y0 }); // repeat dfs for neighbors for (auto dir : dirs) { dfs(grid, x0, y0, i + dir[0], j + dir[1], v); } } // Main function that returns distinct count of islands in // a given boolean 2D matrix int countDistinctIslands(vector<vector<int> >& grid) { int rows = grid.size(); if (rows == 0) return 0; int cols = grid[0].size(); if (cols == 0) return 0; set<vector<pair<int, int> > > coordinates; for (int i = 0; i < rows; ++i) { for (int j = 0; j < cols; ++j) { // If a cell is not 1 // no need to dfs if (grid[i][j] != 1) continue; // vector to hold coordinates // of this island vector<pair<int, int> > v; dfs(grid, i, j, i, j, v); // insert the coordinates for // this island to set coordinates.insert(v); } } return coordinates.size(); } // Driver code int main() { vector<vector<int> > grid = { { 1, 1, 0, 1, 1 }, { 1, 0, 0, 0, 0 }, { 0, 0, 0, 0, 1 }, { 1, 1, 0, 1, 1 } }; cout << "Number of distinct islands is " << countDistinctIslands(grid); return 0; }
Python3
# Python implementation of above approach # 2D array for the storing the horizontal and vertical # directions. (Up, left, down, right dirs = [ [ 0, -1 ], [ -1, 0 ], [ 0, 1 ], [ 1, 0 ] ] # Function to perform dfs of the input grid def dfs(grid, x0, y0, i, j, v): rows = len(grid) cols = len(grid[0]) if i < 0 or i >= rows or j < 0 or j >= cols or grid[i][j] <= 0: return # marking the visited element as -1 grid[i][j] *= -1 # computing coordinates with x0, y0 as base v.append( (i - x0, j - y0) ) # repeat dfs for neighbors for dir in dirs: dfs(grid, x0, y0, i + dir[0], j + dir[1], v) # Main function that returns distinct count of islands in # a given boolean 2D matrix def countDistinctIslands(grid): rows = len(grid) if rows == 0: return 0 cols = len(grid[0]) if cols == 0: return 0 coordinates = set() for i in range(rows): for j in range(cols): # If a cell is not 1 # no need to dfs if grid[i][j] != 1: continue # to hold coordinates # of this island v = [] dfs(grid, i, j, i, j, v) # insert the coordinates for # this island to set coordinates.add(tuple(v)) return len(coordinates) # Driver code grid = [[ 1, 1, 0, 1, 1 ], [ 1, 0, 0, 0, 0 ], [ 0, 0, 0, 0, 1 ], [ 1, 1, 0, 1, 1 ] ] print("Number of distinct islands is", countDistinctIslands(grid)) # This code is contributed by ankush_953
Number of distinct islands is 3
Complejidad temporal: O(rows * cols), donde rows es el número de filas y cols es el número de columnas de la array.
Complejidad del espacio: O(filas * columnas)
Publicación traducida automáticamente
Artículo escrito por ashwinicheerla y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA