Encuentre el número de islas distintas en una array 2D

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++ 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;
}

# 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)