Find length of connected cells of 1s-CodePudding

I wrote code to find the length of connected cells of 1s. But it hits segfault. I did my best to debug but i don't get any clue. Greatly appreciate any inputs!

input 2d array:

output: 5

I am simply trying to find max length from all 8 directions of a given cell. I repeat that for all cells in the 2d-array and find the max length of connected 1's. using the backtracking/recursion method.

Code:

#include<stdio.h>
void print_arr(int arr[5][5], int row, int col) {

    int r, c;
    for (r = 0; r < row; r  ) {
        for (c = 0; c < col; c  )
            printf("%d ", arr[r][c]);
        printf("\n");
    }
}

int find_conneted_len_dir(int arr[5][5], int max_row, int max_col, int org_r, int org_c) {
    int dir_r;
    int dir_c;
    int dir_max = 0;
    int cur_max = 0;
    //printf("dir %d, %d\n",org_r,org_c);
    if ((org_r < 0) || (org_r >= 5) || (org_c < 0) || (org_c >= 5))
        return 0;

    if (arr[org_r][org_c] == 0)
        return 0;

    for (dir_r = -1; dir_r <= 1; dir_r  ) {
        for (dir_c = -1; dir_c <= 1; dir_c  ) {
            if ((dir_r == 0) && (dir_c == 0))
                continue;

            if (((org_r   dir_r) < 0) || ((org_r   dir_r) >= 5) || ((org_c   dir_c) < 0) || ((org_c   dir_c) >= 5))
                continue;
            //printf("from %d - %d : \n", org_r   dir_r, org_c   dir_c);
            if (arr[org_r   dir_r][org_c   dir_c] == 1 ) {
                cur_max = 1   find_conneted_len_dir(arr, max_row, max_col, org_r   dir_r, org_c   dir_c);
                //printf("-->cur_max = %d\n", cur_max);
                if (cur_max > dir_max)
                    dir_max = cur_max;
            }
        }
    }
    return dir_max;
}

int find_conneted_len(int arr[5][5], int row, int col) {
    int r, c;
    int max_row = row;
    int max_col = col;
    int max_len = 0;
    int len = 0;
    for (r = 0; r < max_row; r  ) {
        for (c = 0; c < max_col; c  ) {
            //printf("from top %d - %d : ", r, c);
            if (arr[r][c] != 0) {
                len = find_conneted_len_dir(arr, max_row, max_col, r, c);
                //printf("top len = %d\n", len);
                if (len > max_len)
                    max_len = len;
            }
        }
    }

    return max_len;
}

int main() {
    int arr[5][5] = {
            {0, 0, 1, 0, 0},
            {1, 1, 1, 0, 0},
            {0, 0, 1, 0, 1},
            {1, 0, 0, 1, 1},
            {0, 1, 0, 1, 1},
    };
    int row = 5, col = 5;

    print_arr(arr, row, col);
    int max_len = find_conneted_len(arr, row, col);
    printf("max_len = %d\n", max_len);

    return 0;
}

CodePudding user response：

The problem is that you keep revisiting back and forth the same neighboring cells. This leads to an infinite recursion, depleting the stack.

A solution is to mark the visited cells, by replacing their 1 with a 0.

There is also another issue in your code. There is no need to take maximums of separate counts made by recursive calls. No, these counts all belong to the same connected area, so they should accumulate. So just use one count variable, and not two.

Here is a proposed change for your function:

int find_conneted_len_dir(int arr[5][5], int max_row, int max_col, int org_r, int org_c) {
    int dir_r;
    int dir_c;
    int count = 1; // Use one counter only, and count the current cell

    if ((org_r < 0) || (org_r >= 5) || (org_c < 0) || (org_c >= 5))
        return 0;

    if (arr[org_r][org_c] == 0)
        return 0;

    arr[org_r][org_c] = 0; // clear it

    for (dir_r = -1; dir_r <= 1; dir_r  ) {
        for (dir_c = -1; dir_c <= 1; dir_c  ) {
            if ((dir_r == 0) && (dir_c == 0))
                continue;
            if (((org_r   dir_r) < 0) || ((org_r   dir_r) >= 5) || ((org_c   dir_c) < 0) || ((org_c   dir_c) >= 5))
                continue;
            if (arr[org_r   dir_r][org_c   dir_c] == 1 ) {
                count  = find_conneted_len_dir(arr, max_row, max_col, org_r   dir_r, org_c   dir_c);
            }
        }
    }
    return count;
}

CodePudding user response：

Your code returns a stack overflow error (3221225725). That means your program ran out of memory due to calling one recursive function too many times. It would likely never stop by itself.

find_conneted_len_dir always evaluates if (arr[org_r dir_r][org_c dir_c] == 1 ) to true at some point, no matter what input values are. This is causing it to repeat itself infinitely.