Number of Islands: análisis del problema

< # Lees dos enteros, n y m, que representan las dimensiones de la matriz
n = int(input())
m = int(input())

# Creas una matriz llamada "matrix" para almacenar los valores binarios
matrix = []

# Llenas la matriz leyendo las filas de la entrada estándar
for __ in range(0, n):
    a = input().split()  # Lees una línea y la divides en números
    b = [int(i) for i in a]  # Conviertes los números a enteros
    matrix.append(b)  # Agregas la fila a la matriz

# Definición de la función dfs (Depth-First Search)
def dfs(matrix, node, visited):
    # Marca el nodo actual como visitado y lo establece en 0 en la matriz
    visited[(node[0], node[1])] = True
    matrix[node[0]][node[1]] = 0

    # Explora las celdas vecinas en las cuatro direcciones: arriba, abajo, derecha e izquierda
    # Si una celda vecina contiene un 1 y no ha sido visitada, llama recursivamente a dfs
    # para explorar esa celda vecina

    # Arriba
    if node[0] - 1 >= 0 and matrix[node[0] - 1][node[1]] == 1 and (node[0] - 1, node[1]) not in visited:
        dfs(matrix, [node[0] - 1, node[1]], visited)

    # Abajo
    if node[0] + 1 < n and matrix[node[0] + 1][node[1]] == 1 and (node[0] + 1, node[1]) not in visited:
        dfs(matrix, [node[0] + 1, node[1]], visited)

    # Derecha
    if node[1] + 1 < m and matrix[node[0]][node[1] + 1] == 1 and (node[0], node[1] + 1) not in visited:
        dfs(matrix, [node[0], node[1] + 1], visited)

    # Izquierda
    if node[1] - 1 >= 0 and matrix[node[0]][node[1] - 1] == 1 and (node[0], node[1] - 1) not in visited:
        dfs(matrix, [node[0], node[1] - 1], visited)

# Inicializas un diccionario "visited" para realizar un seguimiento de las celdas visitadas
visited = {}

# Inicializas una variable "a" para contar el número de componentes conexas
a = 0

# Recorres todas las celdas de la matriz
for i in range(n):
    for j in range(m):
        if matrix[i][j] == 1:
            # Si encuentras una celda con un 1, incrementas el contador "a" y llamas a dfs
            a += 1
            dfs(matrix, (i, j), visited)

# Imprimes el número total de componentes conexas
print(a)

> 

Hola 😄, podría empezar a hacer una búsqueda recursiva de la siguiente manera:
.

.
Entrar en una casilla, lo primero que hago es marcar la casilla con un # y luego buscar en las 4 direcciones recursivamente.
.
Si la casilla es 0 o # significa que hay agua o ya he pasado por ahí. Si es 1 sigo buscando.
.
Cuando encuentre que las cuatro direcciones son 0 significa que hay una isla, entonces aumento mi contador de islas, que por comodidad lo tendría global.
.

.
Al final mi matriz quedaría de la siguiente manera:
.

.
Significaría que ya he terminado de buscar islas.

Este es probelma con el que se eseña bfs, en la uva hay un problema para ponerlo en practica 11094 - Continents

Mi solución

def scan_for_near_islands(row, column, matrix, checked_stack):
    for pos in [(row-1, column),(row,column+1),(row+1, column),(row, column-1)]:
        if pos not in checked_stack:
            checked_stack.append(pos)
            try:
                if matrix[pos[0]][pos[1]] == 1:
                    scan_for_near_islands(pos[0], pos[1], matrix, checked_stack)
            except IndexError:
                pass

def find_islands_in_matrix(matrix, checked_stack = []):
    total_island_sum = 0
    for row, column in zip(range(len(matrix)),range(len(matrix[0]))):
        if (row, column) not in checked_stack:
            checked_stack.append((row, column))
            if matrix[row][column] == 1:
                scan_for_near_islands(row, column, matrix, checked_stack)
                total_island_sum += 1
        
    return total_island_sum