0

Необходимо найти соседние элементы двумерного массива, как и представлено в примере:

 { { 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;
}

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

2
  • Это что за хамство? Человек потратил время на ответ, отвечал Вам в комментариях. Вы взяли и все стерли. На что, спрашивается, он отвечал?
    – user176262
    Commented 19 нояб. 2021 в 18:51
  • Перечитайте мой комментарий. Подумайте.
    – user176262
    Commented 19 нояб. 2021 в 19:01

1 ответ 1

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

4
  • Мне кажется, вашу функцию не так просто переделать, чтобы добиться работоспособности
    – MBo
    Commented 18 нояб. 2021 в 9:14
  • У меня не на чем написать на Jаva, для онлайн-компилятора это длинновато. Я не использовал в питоне никаких специфических конструкций, кроме задания матриц - но это-то сообразите, как сделать на Java. Или сделайте заготовку на ideone.com - класс, задание матриц, вывод матриц, объявление одной из функций , и киньте ссылку, а то я не уверен, что у меня рабочий код получится.
    – MBo
    Commented 18 нояб. 2021 в 10:10
  • Ещё раз взглянул на код - рабочие функции ничем не отличаются от джавы, кроме объявления типов параметров, скобок в ифе, и точек с запятой.
    – MBo
    Commented 18 нояб. 2021 в 11:37
  • у меня наконец то все получилось, вы не представляете насколько мне помогли премного благодарен! <3 Commented 18 нояб. 2021 в 13:02

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.