在 Javascript 中将多个岛屿转换为多个国家的解决方案

Question

原题说要算岛的个数（把1的实体连成0的海）

例如：

0001
1001
0110

应该return3因为有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

应该return 5 因为矩阵中有 5 个实体。

Answer 1

您可以交出实际值，只查找相邻的相同值。

我为找到的 islands/countries 添加了一些视觉效果。

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

跟踪当前单元格所属的 ID（按 indices 数组中的索引）

并“合并”实例的 ID，其中 value === left && value === top（两个索引包含相同的 ID）

所以这张地图中的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;
}

在 Javascript 中将多个岛屿转换为多个国家的解决方案

Transform a number of islands into a number of countries solution in Javascript

javascript

arrays

matrix

depth-first-search

ecmascript-6