Рекурсивная функция для поиска, поиска и изменения определенных ячеек на основе критериев

Question

Я пытаюсь в C написать рекурсивную функцию, которая принимает в качестве входных данных матрицу NxM и находит, проверяет конкретные ячейки и изменяет их содержимое в зависимости от сценария.

Исходная матрица

Матричные элементы:

   1 2 3 4 5 6 7 8
------------------
1| 1 6 7 4 4 1 2 8
2| 1 3 6 3 3 1 3 4
3| 3 4 1 5 7 8 5 1
4| 1 7 8 6 2 6 4 4
5| 7 8 1 6 2 2 7 1
6| 3 8 4 3 1 6 8 6
7| 3 8 7 5 4 6 6 6
8| 7 2 2 1 7 4 6 8

На основе матрицы, подобной приведенной выше, пользователь указывает местоположение конкретной ячейки, например, позиция (5,6) для целого числа 2. Я хочу, чтобы рекурсивная функция проверяла ячейки в четырех направлениях: вверх, вниз, влево, вправо и, если она находила одно и то же целое число, меняла их на 0. Это будет продолжаться для всех «соседских» ячеек. В этом примере все двойки в позициях (5,6), (5,5) и (4,5) изменятся на 0.

Другой пример: пользователь задает местоположение, то есть позицию (8,7) для целого числа 6. Рекурсивная функция должна найти и изменить все 6s в позициях (8,7), (7,7), (7,8), (7,6 ), (6,6), (6,8) и установите их в 0с.

    void destroy(int (*arr), int rows, int cols,int search,int rowin, int colin) //rows: total rows of matrxi, cols:total cols of matrix, rowin and colin are the x,y co ordinates of the cell that the user wants to destroy and search has the int i.e 6 ..
{
    int i, j;

    printf("\n");
    printf("\n");

    int count = 0,temp = 0;

    for (j = 0; j < cols; j++) {
    for (i = 0; i < rows; i++) {

          if (*(arr + i*cols + j)== search) {
          if (*(arr + (i-1)*cols + j) == search){//check neighborhood cell
            count++; //counter to know how many similar neighborhood integers have been found
            (*(arr + i*cols + j)= 0);
            *(arr + (i-1)*cols + j) = 0;    
            destroy(int (*arr), int rows, int cols,int search, j, i)   //call recursive function to check the neighborhood cells of the new position  i,j           

        }

      }     
}
}
}

Answer 1

Вам не нужны for петли, а четыре рекурсивных вызова для проверки каждой окрестности.

   void destroy(int *arr, int rows, int cols,int search,int rowin, int colin)
    {
         if (rowin>=rows || colin >= cols || rowin < 0 || colin <0) 
             return; //base condition

         if (arr[rowin*cols+colin] == search)
         {
              arr[rowin*cols+colin] = 0;
              destroy(arr, rows, cols, search, rowin+1, colin);
              destroy(arr,  rows, cols, search, rowin, colin+1);
              destroy(arr,  rows, cols, search, rowin-1, colin);
              destroy(arr,  rows, cols, search, rowin, colin-1);

         }
    }

Answer 2

Обратите внимание, что в C индекс массива начинается с нуля (а не с одного).

Вот пример, в котором используется матрица (или массив массивов).

#include <stdio.h>

void destroy(int value, int r, int c, int r_size, int c_size, int arr[][r_size])
{
    if (value != arr[r][c]) return;  // Nothing to do
    arr[r][c] = 0;
    if (r+1 < r_size) destroy(value, r+1, c, r_size, c_size, arr); // DOWN
    if (r-1 >= 0) destroy(value, r-1, c, r_size, c_size, arr);     // UP
    if (c+1 < c_size) destroy(value, r, c+1, r_size, c_size, arr); // RIGHT
    if (c-1 >= 0) destroy(value, r, c-1, r_size, c_size, arr);     // LEFT
}


void pm(int r_size, int c_size, int arr[r_size][r_size])
{
    printf("-------------------------------------------\n");
    for (int r=0; r < r_size; ++r)
    {
        for (int c=0; c < c_size; ++c)
        {
            printf("%d ", arr[r][c]);
        }
        printf("\n");
    }
}
#define MSIZE 8

int main(void) {
    int arr[MSIZE][MSIZE] =
    {
        {1, 6, 7, 4, 4, 1, 2, 8},
        {1, 3, 6, 3, 3, 1, 3, 4},
        {3, 4, 1, 5, 7, 8, 5, 1},
        {1, 7, 8, 6, 2, 6, 4, 4},
        {7, 8, 1, 6, 2, 2, 7, 1},
        {3, 8, 4, 3, 1, 6, 8, 6},
        {3, 8, 7, 5, 4, 6, 6, 6},
        {7, 2, 2, 1, 7, 4, 6, 8}
    };

    pm(MSIZE, MSIZE, arr);
    destroy(arr[7][6], 7, 6, MSIZE, MSIZE, arr);
    pm(MSIZE, MSIZE, arr);

    return 0;
}

Выход:

-------------------------------------------
1 6 7 4 4 1 2 8 
1 3 6 3 3 1 3 4 
3 4 1 5 7 8 5 1 
1 7 8 6 2 6 4 4 
7 8 1 6 2 2 7 1 
3 8 4 3 1 6 8 6 
3 8 7 5 4 6 6 6 
7 2 2 1 7 4 6 8 
-------------------------------------------
1 6 7 4 4 1 2 8 
1 3 6 3 3 1 3 4 
3 4 1 5 7 8 5 1 
1 7 8 6 2 6 4 4 
7 8 1 6 2 2 7 1 
3 8 4 3 1 0 8 0 
3 8 7 5 4 0 0 0 
7 2 2 1 7 4 0 8 

Версия 2

Эта версия немного отличается, потому что она изменяет элементы, только если найден хотя бы один сосед. Также подсчитывается количество изменений.

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

int destroy_rec(int value, int r, int c, int r_size, int c_size, int arr[][r_size])
{
    if (value != arr[r][c]) return 0;  // Nothing to do
    int changed = 1;
    arr[r][c] = 0;
    if (r+1 < r_size) changed += destroy_rec(value, r+1, c, r_size, c_size, arr); // DOWN
    if (r-1 >= 0) changed += destroy_rec(value, r-1, c, r_size, c_size, arr);     // UP
    if (c+1 < c_size) changed += destroy_rec(value, r, c+1, r_size, c_size, arr); // RIGHT
    if (c-1 >= 0) changed += destroy_rec(value, r, c-1, r_size, c_size, arr);     // LEFT
    return changed;
}

int destroy(int r, int c, int r_size, int c_size, int arr[][r_size])
{
    if (r+1 < r_size && arr[r+1][c] == arr[r][c]) return destroy_rec(arr[r][c], r, c, r_size, c_size, arr);
    if (r-1 >= 0 && arr[r-1][c] == arr[r][c]) return destroy_rec(arr[r][c], r, c, r_size, c_size, arr);
    if (c+1 < c_size && arr[r][c+1] == arr[r][c]) return destroy_rec(arr[r][c], r, c, r_size, c_size, arr);
    if (c-1 >= 0 && arr[r][c-1] == arr[r][c]) return destroy_rec(arr[r][c], r, c, r_size, c_size, arr);
    return 0;
}

void pm(int r_size, int c_size, int arr[r_size][r_size])
{
    printf("-------------------------------------------\n");
    for (int r=0; r < r_size; ++r)
    {
        for (int c=0; c < c_size; ++c)
        {
            printf("%d ", arr[r][c]);
        }
        printf("\n");
    }
    printf("-------------------------------------------\n");
}
#define MSIZE 8

int main(void) {
    int arr[MSIZE][MSIZE] =
    {
        {1, 6, 7, 4, 4, 1, 2, 8},
        {1, 3, 6, 3, 3, 1, 3, 4},
        {3, 4, 1, 5, 7, 8, 5, 1},
        {1, 7, 8, 6, 2, 6, 4, 4},
        {7, 8, 1, 6, 2, 2, 7, 1},
        {3, 8, 4, 3, 1, 6, 8, 6},
        {3, 8, 7, 5, 4, 6, 6, 6},
        {7, 2, 2, 1, 7, 4, 6, 8}
    };

    pm(MSIZE, MSIZE, arr);
    int changed = destroy(7, 6, MSIZE, MSIZE, arr);
    printf("%d cells changed\n", changed);
    pm(MSIZE, MSIZE, arr);

    int (*dyn_arr)[MSIZE] = malloc(MSIZE * sizeof *dyn_arr);
    return 0;
}

Выход:

-------------------------------------------
1 6 7 4 4 1 2 8 
1 3 6 3 3 1 3 4 
3 4 1 5 7 8 5 1 
1 7 8 6 2 6 4 4 
7 8 1 6 2 2 7 1 
3 8 4 3 1 6 8 6 
3 8 7 5 4 6 6 6 
7 2 2 1 7 4 6 8 
-------------------------------------------
6 cells changed
-------------------------------------------
1 6 7 4 4 1 2 8 
1 3 6 3 3 1 3 4 
3 4 1 5 7 8 5 1 
1 7 8 6 2 6 4 4 
7 8 1 6 2 2 7 1 
3 8 4 3 1 0 8 0 
3 8 7 5 4 0 0 0 
7 2 2 1 7 4 0 8 
-------------------------------------------

Answer 3

Я не знаю, чего вы хотите достичь с этим, потому что в вашем коде вы уже проходите через весь массив и после проверки одного элемента вы хотите снова пройти. На мой взгляд, вам не нужна другая итерация для удаления элементов. Вы можете выполнить это за одну итерацию. Если искомый элемент существует, удалите соседние элементы. (i,j => (i-1,j : i+1,j : i,j-1 : i,j+1))
Таким образом, вам может потребоваться установить некоторые значения индекса, чтобы избежать неопределенного поведения.