Страницы

Поиск по вопросам

среда, 5 июня 2019 г.

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

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

На рисунке 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; }


Ответ

Для поиска групп используем классический алгоритм заливки
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: добавил подсчёт количества элементов в группе.

Комментариев нет:

Отправить комментарий