"Дружественные" элементы двойного массива Java

Question

Будем называть «дружественными» элементами для двумерного массива такие элементы, которые соединяются с данным элементом одной из сторон и имеют одно и то же значение, а также все дружественные элементы для дружественных элементов данного элемента. Составить для переданного двумерного массива новый массив, в котором каждый элемент будет содержать информацию о количестве дружественных элементов для соответствующего элемента в переданном массиве. Пример:

 { { 1, 2, 3, 9, 9 },        { { 0, 5, 0, 2, 2 },
   { 2, 2, 2, 9, 2 },   →      { 5, 5, 5, 2, 0 },
   { 1, 1, 2, 2, 4 } }         { 2, 2, 5, 5, 0 } }

Я реализовал функцию на Java, которая возвращает количество соседей с одинаковым числовым значением (count):

public static int getNeighbours3(int arr[][], int row, int col) {
    int num = 0;
    int count = 0;
    for (int direction = 0; direction < 9; direction++) {
        if (direction != 4 && direction % 2 == 0) {
            continue; // direction только нечетный, т.к считаем только соседей сверху, слева, справа и снизу (диагональ не берем)
        }
        if (direction == 4) { // direction == 4 - число с которым сравниваем соседей
            num = arr[row][col];
            continue;
        }
        int n_row = row + ((direction % 3) - 1);
        int n_col = col + ((direction / 3) - 1);
    }
    for (int i = 0; i < arr.length; i++) {
        for (int j = 0; j < arr[i].length; j++) {
            if (arr[i][j] == num && ((Math.abs(i - row) == 1 && j == col) || (Math.abs(j - col) == 1 && i == row))) {
                count++;
                // return getNeighbours3(arr,i,j); // уходит в бесконечный цикл
                
            }
        }
    }
    return count;
}

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

Answer 1

У вас нет условия останова рекурсии - пройденные ячейки нужно помечать - или в дополнительной матрице, или, если предполагаются только положительные числа - менять знак.

Мне Java не на чем запускать, могу показать на Python - два прохода флудфилла, для подсчёта и для заполнения:

A = [[1, 2, 3, 9, 9],[2, 2, 2, 9, 2],[1, 1, 2, 2, 4]]
r = len(A)
c = len(A[0])
B = [[0]*c for _ in range(r)]
M = [[0]*c for _ in range(r)]

def countff(A, M, r, c, y, x, value):
    if y < 0 or x < 0 or x == c or y == r or M[y][x] > 0 or A[y][x] != value:
        return 0
    M[y][x] = 1
    result = 1
    result += countff(A, M, r, c, y-1, x, value)
    result += countff(A, M, r, c, y, x-1, value)
    result += countff(A, M, r, c, y+1, x, value)
    result += countff(A, M, r, c, y, x+1, value)
    return result

def fill(A, M, B, r, c, y, x, value, fillvalue):
    if y < 0 or x < 0 or x == c or y == r or M[y][x] == 2 or A[y][x] != value:
        return
    M[y][x] = 2
    B[y][x] = fillvalue
    fill(A, M, B, r, c, y-1, x, value,fillvalue)
    fill(A, M, B, r, c, y, x-1, value,fillvalue)
    fill(A, M, B, r, c, y+1, x, value,fillvalue)
    fill(A, M, B, r, c, y, x+1, value,fillvalue)

for y in range(r):
    for x in range(c):
        if M[y][x] == 0:
            cnt = countff(A, M, r, c, y, x, A[y][x])
            fill(A, M, B, r, c, y, x, A[y][x], cnt-1)

print(A)
print(B)


[[1, 2, 3, 9, 9], [2, 2, 2, 9, 2], [1, 1, 2, 2, 4]]
[[0, 5, 0, 2, 2], [5, 5, 5, 2, 0], [1, 1, 5, 5, 0]]

По большому счёту - стоит использовать доработанные алгоритмы для Connected Component Labeling

БЛОГ НА HUSL

"Дружественные" элементы двойного массива Java

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