Este problema me hizo sentir mas tonto que de costumbre xD

Si, a veces estos ejercicios son mas enredados de solventar de lo que parece, aún no lo termino, pero ahí voy... pase ya 10 minutos quemando neuronas.

Ha sido refrescante, la verdad, yo me he aclarado cuando he dejado la matriz un poco de lado y he empezado a pensar en nodos de un grafo cerrado. Usar la matriz sólo como representación de datos pero no como mapa mental ha sido clave para saber cómo resolverlo. Lo más intuitivo para mi ha sido un DFS estándar:

explorar(elemento):
    marcar elemento como visitado

    para cada vecino del elemento:
        si el vecino no está visitado:
            explorar(vecino)