Есть матрица клеток определенного размера. Клетка имеет два состояния: занято и пусто. Нужно сосчитать количество групп клеток и количество клеток в каждой группе. Группой считаются рядом стоящие клетки, но не по диагонали.
На рисунке 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: добавил подсчёт количества элементов в группе.
Комментариев нет:
Отправить комментарий