查找連接單元的長度為1s

我撰寫了代碼來查找 1s 的連接單元的長度。但它遇到了段錯誤。我盡力除錯，但我沒有任何線索。非常感謝任何投入！

輸入二維陣列：

11000
01100
00101
10001
01011

輸出：5

我只是想從給定單元格的所有 8 個方向找到最大長度。我對二維陣列中的所有單元重復此操作，并找到連接 1 的最大長度。使用回溯/遞回方法。

代碼：

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

uj5u.com熱心網友回復：

問題是您不斷地來回訪問相同的相鄰單元格。這導致無限遞回，耗盡堆疊。

一種解決方案是標記訪問的單元格，將它們的 1 替換為 0。

您的代碼中還有另一個問題。沒有必要對遞回呼叫進行最大的單獨計數。不，這些計數都屬于同一個連通區域，所以它們應該累積。所以只使用一個count變數，而不是兩個。

這是您的功能的建議更改：

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

uj5u.com熱心網友回復：

您的代碼回傳堆疊溢位錯誤 ( 3221225725)。這意味著您的程式由于呼叫一個遞回函式的次數過多而耗盡了記憶體。它可能永遠不會自行停止。

find_conneted_len_dir無論輸入值是什么， 總是在某個時候計算if (arr[org_r dir_r][org_c dir_c] == 1 )到。true這導致它無限重復。

標籤：

上一篇：使用來自兩個pandasdf的多個正則運算式驗證多行

下一篇：邊的順序在聯合查找中重要嗎？