Преобразуйте количество островов в решение для количества стран за Javascript

Question

Исходная задача говорит, что нужно подсчитать количество островов (соединенных сущностей из 1 в море из 0).

Например:

0001
1001
0110 

должно возвращать 3, потому что есть 3 острова.

Мне удалось решить эту проблему:

function countIslands(A) {
    const row = A.length;
    const col = A[0].length;
    
    const search = (row, col, A) => {
        if(row < 0 || col < 0 || row > A.length - 1 || col > A[row].length - 1 || A[row][col] === 0) {
            return;
        }
        A[row][col] = 0;
        search(row-1,col,A);
        search(row,col-1,A);
        search(row+1,col,A);
        search(row,col+1,A);
    }
    let count = 0;
    A.forEach((row, index) => {
        row.forEach((value, indexI) => {
            if(value === 1) {
                search(index, indexI, A);
                count++;
            }
        })
    })
    return count;
}

все работает нормально. Но есть ли способ изменить его (в идеале не много), чтобы он мог подсчитывать страны?

Например:

1122
1223
5521

должен возвращать 5, потому что есть 5 сущностей в матрице.

Answer 1

Вы можете передать фактическое значение и искать только соседние одинаковые значения.

Я добавляю некоторую визуализацию для найденных островов / стран.

function countIslands(A) {
    const row = A.length;
    const col = A[0].length;

    const search = (row, col, A, value) => {
        if (row < 0 || col < 0 || row >= A.length || col >= A[row].length || A[row][col] !== value) {
            return;
        }
        A[row][col] = 0;
        search(row - 1, col, A, value);
        search(row, col - 1, A, value);
        search(row + 1, col, A, value);
        search(row, col + 1, A, value);
    }
    let count = 0;
    A.forEach((row, index) => {
        row.forEach((value, indexI) => {
            if (value !== 0) {

                A.forEach(a => console.log(...a));
                console.log('');

                search(index, indexI, A, value);
                count++;
            }
        })
    })
    A.forEach(a => console.log(...a))
    return count;
}

console.log(countIslands([[1, 1, 2, 2], [1, 2, 2, 3], [5, 5, 2, 1]]));

.as-console-wrapper { max-height: 100% !important; top: 0; }

Answer 2

Вместо вашего рекурсивного подхода вы можете решить эту проблему за один проход от верхнего левого угла к нижнему правому.

Он создает массив уникальных идентификаторов для каждой новой найденной территории. value !== empty && value !== left && value !== top

отслеживает, к какому идентификатору принадлежит текущая ячейка (по индексу в массиве indices)

и «объединяет» идентификаторы для экземпляров, где value === left && value === top (два индекса содержат с тем же идентификатором)

, так что number of unique IDS === number of distinct territories на этой карте.

function replace(array, oldValue, newValue) {
  //console.log("replace", oldValue, newValue);
  for (let i = 0; i < array.length; ++i) {
    if (array[i] === oldValue) array[i] = newValue
  }
  return newValue;
}

function countIslands(rows, empty = "0") {
  let prev = []; // previous row to determine the top value
  const indices = []; // may contain differrent indices that point to the same ID
  const ids = []; // initially unique IDS, will contain dupes when IDs get "merged"

  for (let row of rows) {
    for (let i = 0; i < row.length; ++i) {
      const value = row[i];
      if (value === empty) {
        continue;
      }
      // current cell is not "empty"

      const top = prev[i] || empty;
      const left = row[i - 1] || empty;

      if (value === left && value === top) {
        // merge ids (think an u-shape where you started at two ends, not knowing in advance that they will meet)
        indices[i] = replace(ids, indices[i - 1], indices[i]);
      } else if (value === left) {
        // current cell belongs to left cell, copy the index
        indices[i] = indices[i - 1];
      } else if (value !== top) {
        // new country, create new id
        indices[i] = ids.length;
        ids[ids.length] = ids.length; // doesn't matter, as long as it is unique.
      }
    }
    prev = row;
  }

  //the number of countries === number of distinct IDs left. 
  return new Set(ids).size;
}
// 9
const map = `
777788
711227
712237
755217
887777`;

/*
// this is as intertwined as it gets, 
// 2 spirals
const map = `
3333333333
2222222223
2333333323
2322222323
2323332323
2323232323
2323222323
2323333323
2322222223
2333333333`;
*/

console.log(countIslands(map.trim().split("\n").map(row => [...row.trim()])));

.as-console-wrapper {
  max-height: 100% !important;
  top: 0;
}