Как найти и сохранить группы значений в двумерном массиве?

Question

Я работаю с двумерным массивом, который содержит значения в каждой точке, и мне нужно найти способ вычислить и вернуть количество групп, составленных из значений, смежных с одним и тем же значением.Например:

+ - -
+ - -
+ + +

В этой версии массива 3x3 в формате ASCII будут группы из двух значений: «+» и «-».Я бы определил этот массив, чтобы иметь две разные группы, основанные на смежности.Если два квадрата не соединены путем смежности, они не будут в одной группе.

3 группы:

+ - -
- - -
+ - -

5 групп:

+ - +
- - -
+ - +

Как я могу написать алгоритм, который мог бы найти количество групп, их значения и позиции?

Спасибо за помощь!

Answer 1

Алгоритм, который вы ищете: Flood Fill .Чтобы найти группы, начните с [0, 0] в вашем массиве и заполните заливку, чтобы найти все подключенные ячейки с одинаковым значением, помечая их как «завершенные» на ходу.Как только заливка завершается, список посещенных вами ячеек становится вашей первой группой.Затем сканируйте массив, пока не найдете ячейку, не помеченную как завершенную, и начните другую заливку оттуда, чтобы найти следующую группу.Повторяйте, пока все ячейки не будут отмечены как завершенные.

Answer 2

Мы можем решить эту проблему, смоделировав ее как график следующим образом:

• Создать вершину для каждой ячейки в массиве
• Добавить ребро между двумя вершинами, если они смежны в массиве и имеют одинаковый «тип»

Так, например, для этого массива:

+ - -     
+ - -     
+ + +

список смежностей представление нашего графа будет (здесь вершина помечена как координата, подобная 0,0, которая соответствует ячейке в array[0][0]):

0,0 -> 1,0
0,1 -> 0,2  1,1
0,2 -> 0,1  1,2
1,0 -> 0,0  2,0
1,1 -> 0,1  1,2
1,2 -> 1,1  0,2
2,0 -> 1,0  2,1
2,1 -> 2,0  2,2
2,2 -> 2,1

, который визуально выглядит следующим образом (горизонтальные ребра представлены как ...):

+   -...-     
|   |   |
+   -...-     
|
+...+...+

Обратите внимание, что наша конструкция графика соответствует тому, что мы хотим на высоком уровне (т.е.аналогичные "регионы").Теперь нам нужно посчитать эти регионы.Для этого мы можем использовать поиск в глубину .

Наша стратегия - запустить DFS в любой вершине и завершить ее.Это полностью покроет область, которой принадлежала начальная вершина.Мы продолжим делать это для всех вершин, которые еще не были затронуты какими-либо DFS, и посчитаем, сколько раз нам нужно выполнить эти DFS.

Это более широко известно как подключающие компоненты проблема.Этот алгоритм для определения количества компонентов для нашего конкретного случая потребует O (n ^ 2) времени для массива nxn , потому что у нас будет n ^ 2 вершин и меньше n ^ 2 ребер (временная сложность DFS составляет O (V + E) ).

Вот рабочее решение в javascript, основанное наприведенный выше алгоритм (тесты для ваших примеров внизу):

function getGroups(array) {
  const graph = buildGraph(array);
  const components = getConnectedComponents(graph);
  return components;
}

function getConnectedComponents(graph) {
  let componentId = 0,
    vertexComponent = {},
    marked = new Set();

  let dfs = function(source) {
    marked.add(source);
    vertexComponent[source] = componentId;
    for (let u of graph[source]) {
      if (!marked.has(u)) dfs(u);
    }
  }

  for (let v in graph) {
    if (!marked.has(v)) {
      dfs(v); // start dfs from an unmarked vertex
      componentId++; // dfs must have "touched" every vertex in that component, so change componentId for the next dfs
    }
  }
  return vertexComponent;
}

function buildGraph(grid) {
  // builds an adjacency list (set) graph representation from a 2d grid
  let g = {};
  grid.forEach((row, i) => {
    row.forEach((cell, j) => {
      let v = i + ',' + j; // vertex label ( e.g 0,1 )
      if (!(v in g)) g[v] = new Set();
      getNeighbors(grid, i, j).forEach(n => {
        if (!(n in g)) g[n] = new Set();
        g[v].add(n);
        g[n].add(v);
      });
    });
  });
  return g;
}

function getNeighbors(grid, i, j) {
  // returns neighboring cells of the same type as grid[i][j]
  let n = [];
  let color = grid[i][j];
  if (i - 1 >= 0 && grid[i - 1][j] === color) n.push([i - 1, j].join());
  if (j - 1 >= 0 && grid[i][j - 1] === color) n.push([i, j - 1].join());
  if (i + 1 < grid.length && grid[i + 1][j] === color) n.push([i + 1, j].join());
  if (j + 1 < grid[0].length && grid[i][j + 1] === color) n.push([i, j + 1].join());
  return n;
}

// Let's do some testing

let array = [
  [0, 1, 1],
  [0, 1, 1],
  [0, 0, 0]
];
let arrayGroups = getGroups(array);
console.log(arrayGroups);
console.log('Total groups: ', new Set(Object.values(arrayGroups)).size);

array = [
  [0, 1, 1],
  [1, 1, 1],
  [0, 1, 1]
];
arrayGroups = getGroups(array);
console.log(arrayGroups);
console.log('Total groups: ', new Set(Object.values(arrayGroups)).size);

array = [
  [0, 1, 0],
  [1, 1, 1],
  [0, 1, 0]
];
arrayGroups = getGroups(array);
console.log(arrayGroups);
console.log('Total groups: ', new Set(Object.values(arrayGroups)).size);