Сосчитать определенное количество элементов в группе

#java #логика

Есть матрица клеток определенного размера. Клетка имеет два состояния: занято и пусто.
Нужно сосчитать количество групп клеток и количество клеток в каждой группе. Группой
считаются рядом стоящие клетки, но не по диагонали. 



На рисунке 4 группы: в 1-ой группе 6 клеток, в остальных - по одной.

Пытался делать сначала функцию для проверки только одной группы. Если группа найдена,
то считаем кол-во клеток в ней и для этих клеток делаем состояние - пусто, чтобы при
следующей проверке эта группа уже "не мешалась". Основная проблема возникла, конечно
же, в условии нахождения группы. Пытался сделать что-то такое, но потом понял, что
это бред, плюс за границы массива вываливаемся. Как можно реализовать эту проверку?

public int getNumberCells(final Cell cellOccupied) {
        int numberRows = field.getNumberRows();
        int numberColumns = field.getNumberColumns();
        int count = 0;

        for (int i = 0; i < numberRows; i++) {
            for (int j = 0; j < numberColumns; j++) {
                if (field.getCell(i, j) == field.getCell(i, j + 1) &&
                        field.getCell(i, j) == cellOccupied) {
                            count++;
                }

                if (field.getCell(i, j) == field.getCell(i + 1, j) &&
                        field.getCell(i, j) == cellOccupied) {
                            count++;
                }
            }
       }
       return count;
}

    

Ответы

Ответ 1

Для поиска групп используем классический алгоритм заливки.

public class Test {

    static final int columns = 8;
    static final int rows = 3;

    static int[][] matrix = {
        { 0,0,1,1,1,0,1,0 },
        { 0,1,1,0,0,0,0,1 },
        { 0,1,0,0,0,0,1,0 }
    };

    static int floodFill(int row, int col) {
        if (row < 0 || col < 0 || col >= columns || row >= rows) return 0;
        if (matrix[row][col] != 1) return 0;
        matrix[row][col] = 2;
        return 1 +
            floodFill(row + 1, col) +
            floodFill(row - 1, col) +
            floodFill(row, col + 1) +
            floodFill(row, col - 1);
    }

    public static void main(String []args) {
        int count = 0;

        for (int row = 0; row < rows; row++) {
            for (int col = 0; col < columns; col++) {
                if (matrix[row][col] == 1) {
                    count++;
                    System.out.println(floodFill(row, col));
                }
            }
        }
        System.out.println(count);
    }
}


Update: добавил подсчёт количества элементов в группе.


Ответ 2

Однопроходный алгоритм без рекурсий:

Перебираем элементы слева-направо и сверху-вниз. Встретив значение 1, заменяем его,
к примеру, на 11. Далее в процессе перебора найдя значение 1, которое граничит с 11,
заменяем на 11, а если не граничит, то на 12 и т.д. В результате, именуем каждую группу
своим уникальным числом.
Параллельно в отдельном массиве считаем сколько раз мы меняли 1 на значение именованной
группы. Скорее всего, возникнут конфликты вроде того, что одной группе были присвоены
разные «имена». Необходимо параллельно определять такие конфликты.
Конфликт разрешается путем ведения третьего массива «синонимов». Если мы имеем 1,
которая граничит например с 11 и 12, то считаем, что 11 и 12 это одна и та же группа.  

Код осуществляющий алгоритм:  

public class Test3 {

    public static void main(String[] args) {
        int[][] matrix = {
            { 0,1,1,0,1,0,0,1 },
            { 0,0,1,1,1,1,0,1 },
            { 1,1,0,1,0,0,1,1 },
            { 1,0,1,0,1,1,0,1 }
        };
        getMatrixGroupsFrom01( matrix );
    }


    public static void getMatrixGroupsFrom01( int[][] matrix ) {
        int width = matrix[0].length;
        int height = matrix.length;
        int groupsCount = 10; // first group - 11, second - 12 ...
        int group1, group2;
        HashMap groupsLength = new HashMap();
        HashMap> synonims = new HashMap>();
        List currentSyn;

        for ( int i = 0; i < width; i++ ) {
            for ( int j = 0; j < height; j++ ) {
                if ( matrix[j][i] == 1 ) { // если текущая ячейка принадлежит пока
неизвестной группе
                    group1 = group2 = 0; // сброс значений
                    if ( j>0 && matrix[j-1][i]>0 ) group1 = matrix[j-1][i]; // группа
сверху
                    if ( i>0 && matrix[j][i-1]>0 ) group2 = matrix[j][i-1]; // группа
снизу
                    if ( group1 == 0 && group2 == 0 ) { // если окружают только нули,
то надо задать новую группу
                        groupsCount++; // новое значение группы
                        matrix[j][i] = groupsCount;
                        groupsLength.put( groupsCount, 1 );
                    } else if ( group1 == 0 || group2 == 0 || group1 == group2 )
{ // если группы одинаковы или одна из них равна 0
                        matrix[j][i] = group1 == 0 ? group2 : group1;
                        groupsLength.put( matrix[j][i], groupsLength.get( matrix[j][i]
)+1 ); // инкремент
                    } else  { // если группы разные, то есть конфликт. Конфликт нужно
разрешить создав синоним
                        if ( group1 > group2 ) { // чтобы работать потом с минимальным
значением
                            int swap = group2;
                            group2 = group1;
                            group1 = swap;
                        }
                        //System.out.println( group1 + " " + group2 );
                        if ( synonims.containsKey( group1 ) ) {
                            currentSyn = synonims.get( group1 );
                        } else {
                            currentSyn = new ArrayList();
                        }
                        if ( currentSyn.indexOf( group2 ) == -1 ) { // если такого
синонима еще нет
                            currentSyn.add( group2 );
                        }
                        synonims.put(group1, currentSyn); // создаем синоним
                        matrix[j][i] = group1;
                        groupsLength.put( group1, groupsLength.get( group1 )+1 );
// инкремент
                    }
                }
                System.out.print( matrix[j][i] + "\t" );
            }
            System.out.print( "\n" );
        }

        // с этого момента есть исчерпывающие данные о группах
        int synSize = synonims.size();
        Integer[] s = {};
        s = synonims.keySet().toArray( s );
        for ( int i=0; i < synSize; i++ ) { // перебираем синонимы
            System.out.print( "\n" + s[i] + " => " );
            List sd = synonims.get( s[i] );
            Iterator cs = sd.iterator();
            while ( cs.hasNext() ) {
                int synVal = cs.next();
                System.out.print( synVal + " " );
                groupsLength.put( s[i], groupsLength.get( s[i] ) + groupsLength.get(
synVal ) ); // добавляем к основной сумме сумму синонима
                groupsLength.remove( synVal ); // удаляем синонимичную сумму
            }
        }

        System.out.println( "\n" );
        s = groupsLength.keySet().toArray( s );
        for ( int i = 0; i < s.length; i++ ) {
            System.out.println( "Group:\t" + s[i] + "\tSize: " + groupsLength.get(
s[i] ) );
        }
    }
}


Результат работы:  

0   0   11  11  
12  0   11  0   
12  12  0   13  
0   12  12  0   
14  12  0   15  
0   12  0   15  
0   0   16  0   
17  17  16  16  

16 => 17 
12 => 14 

Group:  16  Size: 5
Group:  11  Size: 3
Group:  12  Size: 8
Group:  13  Size: 1
Group:  15  Size: 2


Чтобы навести красоту внутри матрицы, нужен еще один проход, в котором синонимы заменяются
одним значением, но для задач, поставленных в вопросе, красота не нужна.