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

Question

Было интересно, может ли кто-нибудь помочь мне с некоторой логикой.

Скажем, у меня есть сетка, которая состоит из:

1 2 3 
1 A B A 
2 A B B 
3 A A B 

Есть 3 группы в этой сетке, которые определяются по стоимости каждой ячейки и всех соседних ячеек, которые имеют одинаковое значение, так предполагающие координат схемы это (колонка, строка):

Группа 1: (1, 1), (1, 2), (1, 3), (2, 3), который имеет значение A

Группа 2: (2, 1), (2, 2), (3, 2), (3, 3), который имеет значение B

Группа 3: (3, 1), которая имеет значение A

Может ли кто-нибудь предложить, как бы определить это программно?

Я думал вдоль линий:

• Использовать цикл для итерации через сетку
  • есть метод, который проверяет верхнюю ячейку, справа, снизу и значение левой ячейки (также учет граничных ячеек)
    • Проверьте, если ячейка имеет то же значение, а затем сохранить его как-то
    • в противном случае это новая группа?
  • Recurse

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

Я бы идеально хотел хранить массив координат, относящихся ко всем группам в сетке.

Answer 1

Я думаю, что концептуально самый простой способ справиться с этим - это рекурсия. Конечно, из-за поддержки подреберной поддержки хвоста Java, итеративное решение было бы более эффективным; Тем не менее рекурсия должна работать для небольших ценностей.

Взгляните на этот пример кода

public static void main(String[] args) { 
    int xBound = 3; 
    int yBound = 3; 
    String[][] grid = new String[][] { 
     {"A", "B", "A"}, 
     {"A", "B", "B"}, 
     {"A", "A", "B"} 
    }; 

    for(int i = 0; i < yBound; i++) { 
     for(int j = 0; j < xBound; j++) { 
      String state = grid[i][j]; 
      List<List<Integer>> group = getGroup(state, j, i, xBound, yBound, grid); 
      if (group.size() != 0) { 
       System.out.println(state + " " + group); 
      } 
     } 
    } 
} 

static List<List<Integer>> getGroup(String state, int xIndex, int yIndex, int xBound, int yBound, String[][] grid) { 
    if (xIndex >= xBound || xIndex < 0 || yIndex >= yBound || yIndex < 0 || grid[yIndex][xIndex].equals("USED")) { 
     return new ArrayList<>(); 
    } else if (grid[yIndex][xIndex].equals(state)){ 
     grid[yIndex][xIndex] = "USED"; 

     List<List<Integer>> ourPosse = new ArrayList<List<Integer>>(); 
     ourPosse.add(Arrays.asList(yIndex, xIndex)); 
     ourPosse.addAll(getGroup(state, xIndex + 1, yIndex, xBound, yBound, grid)); 
     ourPosse.addAll(getGroup(state, xIndex - 1, yIndex, xBound, yBound, grid)); 
     ourPosse.addAll(getGroup(state, xIndex, yIndex + 1, xBound, yBound, grid)); 
     ourPosse.addAll(getGroup(state, xIndex, yIndex - 1, xBound, yBound, grid)); 

     return ourPosse; 
    } else { 
     return new ArrayList<>(); 
    } 
} 

Мы шаг через сетку, пытаясь использовать каждую запись как «корень» новой группы. Если отдельная группа фактически внедрена в эту запись (т. Е. GrpCt! = 0), то мы ее печатаем.

В getGroupMethod мы сначала проверяем, не вышли ли мы из границ сетки или мы уже использовали запись в предыдущей группе. Обратите внимание, что эта проверка выполняется путем изменения сетки, но вместо этого мы можем сохранить заметку.

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

В противном случае мы знаем, что настоящая запись не может быть частью группы.

Редактировать: В терминах асимптотического времени работы, поскольку мы эффективно сохраняем память, устанавливая флаг в сетке и, таким образом, учитывая каждую запись не более 4 раз, у нас есть O (n^2).