Question

По сути, я пытаюсь взять уже существующий двумерный массив чисел 50 x 50 и использую источник, указанный в коде (iy и ix), чтобы найти подключенные ячейки с тем же значением изаменить все неподключенные ячейки на 0. Например, массив, такой как

1 5 3 2 5 5 5
0 1 9 4 5 0 0
3 3 4 5 5 5 5

Используя ячейку в (1,4), я бы тогда получил массив

0 0 0 0 5 5 5
0 0 0 0 5 0 0
0 0 0 5 5 5 5

* 1006.* Мой текущий код просто находит все ячейки с одинаковой высотой, он ничего не делает, чтобы найти подключенные.Это просто не убирает это, само по себе.Я думаю, это проблема с тем, как я прохожу список в циклах for для проверки подключенных ячеек, но я не могу сказать, в чем проблема

Я кодирую это с помощью C. Любая помощь будет принята с благодарностью!

//Get the "height" of the "origin" cell
int height = array[x][y];

//I copy the original array into the new array, 
//but I only copy the cells with values equal to the "height" of the first cell

    for (int i = 0; i <= 50; i++)
    {
      for (int j = 0; j <= 50; j++)
      {
        if (array[i][j] == height)
        {
          newarray[i][j] = array[i][j];
        }
        else
        {
          newarray[i][j] = 0;
        }
      }
    }

// Iterate through the array, starting from the origin cell. 
//If the cell above or to the left isn't connected to it, then turns it into a 0 cell
    for (int i = x; i <= 50; i++)
    {
      for (int j = y; j <= 50; j++)
      {
        if (newarray[i][j] == height)
        {
          if (newarray[i][j-1] == height || newarray[i-1][j] == height)
          {
            newarray[i][j] = height;
          }
          else
          {
            newarray[i][j] = 0;
          }
        }
      }
    }

//Does the same, but does it towards the origin (0,0). If the cell to the right 
//or below isnt connected to it then it turns it into a 0 cell
    for (int i = x; i >= 0; i--)
    {
      for (int j = y; j >= 0; j--)
      {
        if (array[i][j] == height)
        {
          if (newarray[i][j+1] == height || newarray[i+1][j] == height)
          {
            newarray[i][j] = height;
          }
          else
          {
            newarray[i][j] = 0;
          }
        }
      }
    }


}

РЕДАКТИРОВАТЬ:

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

void connectedvals(char array[50][50], char newarray[50][50], int x, int y)
{

int height = array[x][y];
    newarray[x][y] = array[x][y];
    int up = y + 1;
    int down = y - 1;
    int left = x - 1;
    int right = x + 1;

    if (up < 50)
    {
      if (array[x][up] == height)
      {
        newarray[x][up] = height;
        up++;
        connectedvals(array, newarray, x, up)
      }
    }

    if (down >= 0)
    {
      if (array[x][down] == height)
      {
        newarray[x][down] = height;
        down--;
        connectedvals(array, newarray, x, down)
      }
    }

    if (right < 50)
    {
      if (array[right][y] == height)
      {
        newarray[right][y] = height;
        right++;
        connectedvals(array, newarray, right, y)
      }
    }

    if (left >= 0)
    {
      if (array[left][y] == height)
      {
        newarray[left][y] = height;
        left--;
        connectedvals(array, newarray, left, y)
      }
    }
}

Jonathan Leffler · Answer 1 · 10 июня 2019

Существует ряд проблем с рекурсивным решением, в том числе:

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

Вот две версии кода, которые не вылетают.

`conn29.c` - минимально фиксированный

Этот код исправляет точку 2, а результат демонстрирует точку 1.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

enum { SIZE = 13 };

static
void connectedvals(char array[SIZE][SIZE], char newarray[SIZE][SIZE], int x, int y)
{
    if (newarray[x][y] != 0)
        return;
    int height = array[x][y];
    newarray[x][y] = array[x][y];
    int up = y + 1;
    int down = y - 1;
    int left = x - 1;
    int right = x + 1;

    if (up < SIZE)
    {
        if (array[x][up] == height)
        {
            newarray[x][up] = height;
            up++;
            connectedvals(array, newarray, x, up);
        }
    }

    if (down >= 0)
    {
        if (array[x][down] == height)
        {
            newarray[x][down] = height;
            down--;
            connectedvals(array, newarray, x, down);
        }
    }

    if (right < SIZE)
    {
        if (array[right][y] == height)
        {
            newarray[right][y] = height;
            right++;
            connectedvals(array, newarray, right, y);
        }
    }

    if (left >= 0)
    {
        if (array[left][y] == height)
        {
            newarray[left][y] = height;
            left--;
            connectedvals(array, newarray, left, y);
        }
    }
}


static void dump_array(const char *tag, int rows, int cols, char array[rows][cols])
{
    printf("%s (%dx%d):\n", tag, rows, cols);
    for (int i = 0; i < rows; i++)
    {
        for (int j = 0; j < cols; j++)
        {
            putchar(' ');
            if (array[i][j] == 0)
                putchar('.');
            else
                printf("%d", array[i][j]);
        }
        putchar('\n');
    }
}

int main(void)
{
    char base[SIZE][SIZE] = { 0 };
    char trace[SIZE][SIZE] = { 0 };

    // srand(time(0));
    for (int i = 0; i < SIZE; i++)
    {
        for (int j = 0; j < SIZE; j++)
        {
            base[i][j] = (rand() % 12);
            if (base[i][j] > 9)
                base[i][j] = 0;
            if ((rand() % 4) == 0)
                base[i][j] = 5;
        }
    }

    dump_array("Base array", SIZE, SIZE, base);

    int i0 = rand() % SIZE;
    int j0 = rand() % SIZE;

    while (base[i0][j0] != 5)
    {
        i0 = rand() % SIZE;
        j0 = rand() % SIZE;
    }

    printf("i0 = %2d, j0 = %2d, base[%2d][%2d] = %d\n", i0, j0, i0, j0, base[i0][j0]);

    connectedvals(base, trace, i0, j0);

    dump_array("Connected region", SIZE, SIZE, trace);

    return 0;
}

выход

Base array (13x13):
 7 5 5 . . . . 3 7 5 3 9 4
 3 8 1 8 2 7 3 5 5 5 8 6 5
 5 4 5 6 . 5 5 5 . . 7 9 5
 5 3 9 5 5 3 . 5 . 4 5 9 5
 5 1 5 5 5 3 . 5 . 5 5 5 .
 . 5 7 5 3 2 2 4 8 . 8 3 6
 5 1 3 5 6 5 . 2 7 4 2 7 1
 8 . 4 5 5 7 9 . 5 . 5 . 7
 5 9 5 2 . 1 5 5 3 . . 5 5
 . 7 1 8 3 3 5 9 . . 3 3 3
 . 5 1 5 9 9 5 8 5 2 5 . 8
 4 2 9 9 . 5 5 5 . 5 2 4 3
 5 2 5 2 3 5 4 1 5 9 5 5 5
i0 =  5, j0 =  3, base[ 5][ 3] = 5
Connected region (13x13):
 . . . . . . . . . . . . .
 . . . . . . . . . . . . .
 . . . . . . . . . . . . .
 . . . 5 5 3 . . . . . . .
 . . . 5 . 3 . . . . . . .
 . . . 5 . 2 2 4 . . . . .
 . . . 5 . . . . . . . . .
 . . . 5 5 7 . . . . . . .
 . . . . . . . . . . . . .
 . . . . . . . . . . . . .
 . . . . . . . . . . . . .
 . . . . . . . . . . . . .
 . . . . . . . . . . . . .

`conn11.c` - исправлено полностью

Возможно, еще есть место для совершенствования, но это работает.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

enum { SIZE = 13 };

extern void connectedvals(char array[SIZE][SIZE], char newarray[SIZE][SIZE], int x, int y, int value);

void connectedvals(char array[SIZE][SIZE], char newarray[SIZE][SIZE], int x, int y, int value)
{
    /*printf("a[%2d][%2d] = %d\n", x, y, array[x][y]);*/
    if (array[x][y] != value || newarray[x][y] != 0)
        return;
    newarray[x][y] = value;

    if (y + 1 < SIZE)
        connectedvals(array, newarray, x + 0, y + 1, value);
    if (y - 1 >= 0)
        connectedvals(array, newarray, x + 0, y - 1, value);
    if (x + 1 < SIZE)
        connectedvals(array, newarray, x + 1, y + 0, value);
    if (x - 1 >= 0)
        connectedvals(array, newarray, x - 1, y + 0, value);
}

static void dump_array(const char *tag, int rows, int cols, char array[rows][cols])
{
    printf("%s (%dx%d):\n", tag, rows, cols);
    for (int i = 0; i < rows; i++)
    {
        for (int j = 0; j < cols; j++)
        {
            putchar(' ');
            if (array[i][j] == 0)
                putchar('.');
            else
                printf("%d", array[i][j]);
        }
        putchar('\n');
    }
}

int main(void)
{
    char base[SIZE][SIZE] = { 0 };
    char trace[SIZE][SIZE] = { 0 };

    // srand(time(0));
    for (int i = 0; i < SIZE; i++)
    {
        for (int j = 0; j < SIZE; j++)
        {
            base[i][j] = (rand() % 12);
            if (base[i][j] > 9)
                base[i][j] = 0;
            if ((rand() % 4) == 0)
                base[i][j] = 5;
        }
    }

    dump_array("Base array", SIZE, SIZE, base);

    int i0 = rand() % SIZE;
    int j0 = rand() % SIZE;

    while (base[i0][j0] != 5)
    {
        i0 = rand() % SIZE;
        j0 = rand() % SIZE;
    }

    printf("i0 = %2d, j0 = %2d, base[%2d][%2d] = %d\n", i0, j0, i0, j0, base[i0][j0]);

    connectedvals(base, trace, i0, j0, base[i0][j0]);

    dump_array("Connected region", SIZE, SIZE, trace);

    return 0;
}

выход

Base array (13x13):
 7 5 5 . . . . 3 7 5 3 9 4
 3 8 1 8 2 7 3 5 5 5 8 6 5
 5 4 5 6 . 5 5 5 . . 7 9 5
 5 3 9 5 5 3 . 5 . 4 5 9 5
 5 1 5 5 5 3 . 5 . 5 5 5 .
 . 5 7 5 3 2 2 4 8 . 8 3 6
 5 1 3 5 6 5 . 2 7 4 2 7 1
 8 . 4 5 5 7 9 . 5 . 5 . 7
 5 9 5 2 . 1 5 5 3 . . 5 5
 . 7 1 8 3 3 5 9 . . 3 3 3
 . 5 1 5 9 9 5 8 5 2 5 . 8
 4 2 9 9 . 5 5 5 . 5 2 4 3
 5 2 5 2 3 5 4 1 5 9 5 5 5
i0 =  5, j0 =  3, base[ 5][ 3] = 5
Connected region (13x13):
 . . . . . . . . . . . . .
 . . . . . . . . . . . . .
 . . . . . . . . . . . . .
 . . . 5 5 . . . . . . . .
 . . 5 5 5 . . . . . . . .
 . . . 5 . . . . . . . . .
 . . . 5 . . . . . . . . .
 . . . 5 5 . . . . . . . .
 . . . . . . . . . . . . .
 . . . . . . . . . . . . .
 . . . . . . . . . . . . .
 . . . . . . . . . . . . .
 . . . . . . . . . . . . .

Испытательный жгут практически идентичен между двумя программами. Разница заключается в списке аргументов для начального вызова connectedvals(), потому что две реализации имеют разное количество аргументов.

Выбор размера 13 не случаен; это приводит к аккуратному результату с генератором случайных чисел. Матрица генерируется «в случайном порядке», за исключением того, что результат намеренно отклоняется в сторону чисел 0 и 5. Вы вполне можете получить другой результат от функции rand() на вашем компьютере; Я тестировал MacBook Pro с MacOS 10.14.5 Mojave, используя GCC 9.1.0 для компиляции.

Предусмотрено использование времени в качестве начального числа - раскомментирование одной строки. Однако для начального тестирования определенность (повторяемость) более выгодна, чем случайность. Есть много лучших способов посева rand(), чем использование времени; это довольно предсказуемо. Однако такие уточнения выходят за рамки вопроса.

Обратите внимание на использование enum { SIZE = 13 };. Изменяя только один номер, вся программа адаптируется к новым размерам.

Как найти подключенные ячейки с одинаковым значением в массиве

Пожалуйста, войдите или зарегистрируйтесь чтобы ответить на этот вопрос.

1 Ответ

`conn29.c` - минимально фиксированный

`conn11.c` - исправлено полностью

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

Как найти подключенные ячейки с одинаковым значением в массиве

Пожалуйста, войдите или зарегистрируйтесь чтобы ответить на этот вопрос.

1 Ответ

conn29.c - минимально фиксированный

conn11.c - исправлено полностью

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

Нет похожих вопросов

`conn29.c` - минимально фиксированный

`conn11.c` - исправлено полностью