Elimina las islas de una matriz.

Este es el segundo post que hago en esta sección, en esta oportunidad voy a resolver un ejercicio que me cruce en internet, no recuerdo realmente donde, pero me parecio bueno. Es de nivel medio según el sitio donde lo vi.

El enunciado traducido al español va mas o menos así: Dada una matriz que representa una parte de un mapa decimos que la tierra está representado por un uno (1) y el agua por un cero (0). Un pedazo de tierra consiste en una serie de unos (1) adyacentes entre si ya sea arriba, abajo, izquierda o derecha. Por otro lado se considera una isla a un pedazo de tierra que no tiene conexión con los bordes de la matriz. Escribe una función que elimine las islas dentro de la matriz.

Bueno, si entendiste el enunciado de una vez, hermoso, pero si no vamos a tratar de explicarlo por partes y veamos un ejemplo para tenerlo lo más claro posible. Vamos a pensar en la matriz de la figura de abajo:

Aja, tenemos una matriz de 4x4 como ejemplo. El enunciado nos "la tierra está representado por un uno (1) y el agua por un cero (0)", entonces en la matriz M vemos que el elemento M[1][0] es tierra y el elemento M[0][0] es agua.

Otro punto del enunciado dice que "Un pedazo de tierra consiste en una serie de unos (1) adyacentes entre si ya sea arriba, abajo, izquierda o derecha." y de nuevo nos vamos a nuestra matriz M y vemos que los elementos **M[1][0], M[2][0], M[2][1] y M[3][1] forman un pedazo de tierra porque están adyacentes uno al otro en alguna de las cuatro direcciones que se mencionaron. En la figura de abajo se ve más claro.

Ahora, finalmente qué es una isla? El enunciado dice "Por otro lado se considera una isla a un pedazo de tierra que no tiene conexión con los bordes de la matriz". Lo que esto nos define es que todo los pedazos de tierra, es decir todos los unos (1) ya sean conectados como la figura anterior o individuales son una isla si no tienen un uno (1) adyacente que esté en el borde de la matriz, por ejemplo el elemento M[1][2] porque no tiene un uno en la posición de arriba, ni abajo, ni a ninguno de los costados, es decir, esta rodeado de agua; diagonalmente no es valido segun el enunciado y por esto el elemento M[0][3] no sirve como conexión al borde.

Ok, ya explicamos el enunciado y espero que haya quedado claro, entonces lo que deberia hacer nuestra función es eliminar precisamente el elemento M[1][2] como lo muestra la figura.

Bueno, vamos a implementar esto. La idea principal para resolver el problema es la siguiente, voy tener un segundo mapa donde todo es agua, es decir, una segunda matriz donde todos sus elementos son ceros (0), llamemos este mapa noIslandsGrid . Luego me fijo en mi mapa original, la matriz M y voy marcando en el noIslandsGrid los elementos de tierra que NO son una isla. Ahora enumeremos los pasos:

1. Inicializo el noIslandsGrid.
2. Recorrer los cuatro bordes de la matriz M.
   • Parto desde el elemento M[0][0] y voy en sentido horario.
   • Si el elemento es tierra, un uno (1), empiezo a ver los elementos adyacentes.
   • Si es agua sigo al próximo elemento.
3. Si el elemento es tierra entonces me fijo en las posiciones adyacentes en el orden derecha, abajo, izquierda y arriba.
   • Si la posición adyacente está fuera de la matriz paso a la siguiente dirección.
   • Si la posición adyacente es agua paso a la siguiente dirección.
   • Si la posición adyacente ya lo habia marcado antes en el noIslandsGrid paso a la otra dirección.
   • Si pasa todas las condiciones anteriores, es decir la posición es tierra, está dentro de la matriz y no está registrado en el noIslandsGrid entonces lo registro en el noIslandsGrid.
   • Sigo explorando las posiciones adyacentes.
4. Retorno el noIslandsGrid como resultado.

Y por ultimo veamos el código en JavaScrtip de la solución.

1. Inicializo el noIslandsGrid.

const noIslandsGrid = Array(land.length)
  .fill()
  .map(() => Array(land[0].length).fill(0));

2. Recorrer los cuatro bordes de la matriz M.

//Para controlar como nos movemos en los bordes.
//El orden es derecha, abajo, izquierda, arriba. Sentido horario.
 const directions = [
    [0, 1],
    [1, 0],
    [0, -1],
    [-1, 0],
  ];

  //La dirección en la que nos estamos moviendo, empezando hacia la derecha.
  let direction = 0;

  //Cuantas iteraciones tenemos que hacer para recorrer todo el borde.
  //Si nuestra matriz es de ROWxCOL dimensiones, seria dos veces la cantidad de COL más la cantidad de ROW - 2.
  const iterations = land.length * 2 + (land[0].length - 2) * 2;

  //Parto desde el elemento **M[0][0]** y voy en sentido horario.
  let row = 0;
  let col = 0;

  for (let i = 0; i <= iterations; i++) {
    //Si el elemento es tierra, un uno (1), empiezo a ver los elementos adyacentes.
    if (land[row][col] == 1) {
      explore(land, row, col, noIslandsGrid);
    }

    let step = directions[direction];

    //Esta lógica es para controlar el recorrido de los bordes y no es parte del algoritmo que enumeré arriba.
    //Nos fijamos si nuestro próximo paso está dentro de la matriz
    let rowInBound = row + step[0] < land.length && row + step[0] >= 0;
    let colInBound = col + step[1] < land[0].length && col + step[1] >= 0;

    if (!rowInBound || !colInBound) {
      //get the right direction
      direction = (direction + 1) % 4;
      step = directions[direction];
    }

    //Damos el paso
    row += step[0];
    col += step[1];
  }

3. Si el elemento es tierra entonces me fijo en las posiciones adyacentes en el orden derecha, abajo, izquierda y arriba.

const explore = (grid, row, col, noIslandsGrid) => {
  //Si la posición adyacente está fuera de la matriz paso a la siguiente dirección.
  const rowInbound = 0 <= row && row < grid.length;
  const colInbound = 0 <= col && col < grid[0].length;

  if (!rowInbound || !colInbound) return;

  //Si la posición adyacente es agua paso a la siguiente dirección.
  if (grid[row][col] == 0) return;

  //Si la posición adyacente ya lo habia marcado antes en el **noIslandsGrid** paso a la otra dirección.
  if (noIslandsGrid[row][col] == 1) return;

  // * Si pasa todas las condiciones anteriores, es decir la posición es tierra, está dentro de la matriz y no está registrado en el **noIslandsGrid** entonces lo registro en el **noIslandsGrid**.
  noIslandsGrid[row][col] = 1;

  //Sigo explorando las posiciones adyacentes.
  explore(grid, row, col + 1, noIslandsGrid); //right
  explore(grid, row + 1, col, noIslandsGrid); //down
  explore(grid, row, col - 1, noIslandsGrid); //left
  explore(grid, row - 1, col, noIslandsGrid); //up
};

4. Retorno el noIslandsGrid como resultado.

return noIslandsGrid;

Y listo, lo tenemos resuelto. Ahora la complejidad, si no me equivoco el time complexity seria algo como O(iterations) + O(ROWxCOL) y space complexity sería O(ROWxCOL) porque en el peor de los casos, que todos sean tierra, reccoreriamos la matriz completa. Igual esto es aproximado y no es que sea el más experto en big O, pero creo que van por ahi los tiros.

Aca te dejo el repo donde tengo bastantes mas problemas de estos resueltos que poco a poco ire dejando aca en el sitio.

De nuevo gracias, espero que te sirva de referencia y me queda pendiente activar comentarios en el post.... algún día lo haré!