Посчитать количество белых квадратов (java)

Question

int buf = 1;
List<Integer> list = new ArrayList<Integer>();
int array[][] = {
        {1, 0, 0, 0, 0, 0},
        {1, 1, 0, 0, 1, 0},
        {0, 0, 0, 0, 0, 1},
        {1, 1, 0, 0, 0, 0},
        {1, 1, 1, 0, 1, 1}};
for (int i = 0; i < array.length; i++) {
    for (int j = 0; j < array[i].length; j++) {
        System.out.print(array[i][j] + " ");
        if (array[i][j] == 1) {
            list.add(buf++);
        }
    }
    System.out.println(list);
    buf = 1;
    list.removeAll(list);
}

Answer 1

Простейшая задача на поиск связных компонент.

Функция для чтения значения поля

private static int GetMatrixValue(int[][] array, int x, int y) {
    if (x < 0 || y < 0) return 0;
    if (x >= array.length || y >= array[x].length) return 0;
    return array[x][y];
}

Функция для получения количества блоков в айсберге по координатам. Заодно затираем блоки, чтобы 2 раза не ходить.

private static int GetVolume(int[][] array, int x, int y) {
    if (GetMatrixValue(array, x, y) != 1) return 0;
    array[x][y] = 0;
    int ret = 1 + GetVolume(array, x + 1, y) + GetVolume(array, x - 1, y) + GetVolume(array, x, y + 1) + GetVolume(array, x, y - 1);
    return ret;
}

Функция, что рассчитывает количество айсбергов по количеству блоков

private static Map<Integer, Integer> GetConnectedComponentsVolume(int[][] array) {
    HashMap<Integer, Integer> result = new HashMap<>();
    for (int i = 0; i < array.length; i++) {
        for (int j = 0; j < array[i].length; j++) {
            int volume = GetVolume(array, i, j);
            if (volume > 0) result.put(volume, result.getOrDefault(volume, 0) + 1);
        }
    }
    return result;
}

Основная функция

public static void main(String[] args) {

    int array[][] = {
            {1, 0, 0, 0, 0, 0},
            {1, 1, 0, 0, 1, 0},
            {0, 0, 0, 0, 0, 1},
            {1, 1, 0, 0, 0, 0},
            {1, 1, 1, 0, 1, 1}};


    Map<Integer, Integer> volumes = GetConnectedComponentsVolume(array);
    volumes.entrySet().stream().sorted(Comparator.comparing(Map.Entry::getKey))
            .forEach(e -> System.out.println(e.getKey() + "-" + e.getValue()));
}

Вывод

1-2
2-1
3-1
5-1

БЛОГ НА HUSL

Посчитать количество белых квадратов (java)

Ответы (1 шт):