再帰を使用して1に遭遇したときのセグメンテーション

Question

ムーアのネイバーのようなすべてのネイバーをチェックし、ムーアのネイバーを使用して接続されているすべての1についてランダムに生成されたアレイをチェックするために再帰を使用するはずです。私の再帰コードは、ゼロに遭遇したときにうまくいくように見えますが、それに遭遇するとセグメント化エラーが発生します。私はgdbとvalgrindを試しましたが、このエラーが出ました。

Program received signal SIGSEGV, Segmentation fault. 
0x0000000000400a34 in recursive (arr=0x6030b0, xcoord=-1, 
ycoord=0, row=6, 
    col=6) at as4.c:79 
79   if(arr[xcoord][ycoord] == 1) 

と私が入力したときにどこにgdbで（）ここで、私は、だから私は何か間違ったことをmallocingていた場合、私はわからないか、私の再帰はちょうど間違っている場合は、この

#0 0x0000000000400a34 in recursive (arr=0x6030b0, xcoord=-1, 
ycoord=0, row=6, 
col=6) at as4.c:79 

#1 0x0000000000400a61 in recursive (arr=0x6030b0, xcoord=0, 
ycoord=0, row=6, 
col=6) at as4.c:83 

#2 0x0000000000400975 in main (argc=3, argv=0x7fffffffdf48) at 
as4.c:56 

得ます。誰かが私が間違っていることを教えてもらえますか？

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

int recursive(int **arr, int xcoord, int ycoord, int row, int col);//What are the arguments for the recursive function? 

int main(int argc, char** argv) 
{ 
    int i;//counters 
    int j;//counters 
    int xcoord;//x coordinate input 
    int ycoord;//y coordinate input 

    //random number generator thing idk lol 
    srand((unsigned int)time(NULL)); 

    int row = strtol(argv[1], NULL, 0);//ROW from command line arguments (1st number) 
    int col = strtol(argv[2], NULL, 0);//COL from command line arguments (2nd number) 

    int *arrStorage = malloc(row * col * sizeof(int));//dynamically allocating memory for 2d array 
    int **arr = malloc(row * sizeof(int));  //pointer to pointer to array or whatever 

    //intializing array 
    for (i = 0; i < row; i++) 
    { 
      arr[i] = arrStorage + col * i; 
    } 

    //printing out 2d array 
     for (i = 0; i < row; i++) 
    { 
      for (j = 0; j < col; j++) 
     { 
      arr[i][j] = rand() % 2; 
      printf("%d\t", arr[i][j]); 
     } 

     printf("\n"); 
    } 

    printf(" "); 

    //Exit the function when non number is entered 
    //Otherwise continue 
    while(1) 
    { 
     printf("Enter coordinate i,j (Non numeric to quit) \n");  

     if(1!=scanf("%d", &xcoord) || 1!=scanf("%d", &ycoord)) 
     { 
      return 0; 
     } 

     printf("Blob size: %d\n", recursive(arr, xcoord, ycoord, row, col)); 
     printf("The total size it takes up is %d percent \n", recursive(arr, xcoord, ycoord, row, col)/(row*col)); 
    } 

    for (i = 0; i < row; i++) 
    { 
     free(arr[i]); 
    } 
} 

int recursive(int **arr, int xcoord, int ycoord, int row, int col) 
{ 
    int blobsize = 0; 

    //if coordinate is out of bounds or the user puts in too small or big coordinate return 0 
    if(xcoord < 0 && ycoord < 0 && xcoord > row && ycoord > col) 
    { 
     return 0; 
    } 

    //recursively check all the neighbors 
    else 
    { 
     if(arr[xcoord][ycoord] == 1) 
     { 
      blobsize = blobsize + 1; 

      if(recursive(arr, xcoord - 1, ycoord, row, col))//Check up 
      { 
       if(arr[xcoord][ycoord] == 1) 
       { 
        blobsize = blobsize + 1; 
       } 
       return 1; 
      } 

      if(recursive(arr, xcoord - 1, ycoord + 1, row, col))//Check right up 
      { 
       if(arr[xcoord][ycoord] == 1) 
       { 
        blobsize = blobsize + 1; 
       } 
       return 1; 
      } 

      if(recursive(arr, xcoord, ycoord + 1, row, col))//Check right 
      { 
       if(arr[xcoord][ycoord] == 1) 
       { 
        blobsize = blobsize + 1; 
       } 
       return 1; 
      } 

      if(recursive(arr, xcoord + 1, ycoord + 1, row, col))//Check bottom right 
      { 
       if(arr[xcoord][ycoord] == 1) 
       { 
        blobsize = blobsize + 1; 
       } 
       return 1; 
      } 

      if(recursive(arr, xcoord + 1, ycoord, row, col))//Check bottom 
      { 
       if(arr[xcoord][ycoord] == 1) 
       { 
        blobsize = blobsize + 1; 
       } 
       return 1; 
      } 

      if(recursive(arr, xcoord + 1, ycoord-1, row, col)) 
      { 
       if(arr[xcoord][ycoord] == 1) 
       { 
        blobsize = blobsize + 1; 
       } 
       return 1; 
      } 

      if(recursive(arr, xcoord, ycoord-1, row, col)) 
      { 
       if(arr[xcoord][ycoord] == 1) 
       { 
        blobsize = blobsize + 1; 
       } 
       return 1; 
      } 

      if(recursive(arr, xcoord - 1, ycoord - 1, row, col)) 
      { 
       if(arr[xcoord][ycoord] == 1) 
       { 
        blobsize = blobsize + 1; 
       } 
       return 1; 
      }  
     } 
    } 

    return blobsize; 
} 

そして、ええ、私は特定の位置に1が発生した場合は1で、すべての私の隣人とインクリメントblobsizeをチェックするために再帰を使用する必要があります。

Answer 1

再帰が終了せず、プ​​ログラムはスタックオーバーフローのために失敗します。たとえば、6x6の場合は、（4,4）、（5,5）、（4,4）、（5,5）...を無期限に呼び出し、スタックを爆発させます。

free(arrStorage) 
free(arr) 

よう

また

、free両方のポインタのlibc /カーネルはこれを行う方法にfree(a[i])

Answer 2

A本当に良い方法を知っていないので（それはあなたがキューを構築することができますので、最適化することは容易です再帰を使用する代わりに）は、三色アルゴリズムと呼ばれるものを使用することです。

http://www.cs.cornell.edu/courses/cs2112/2012sp/lectures/lec24/lec24-12sp.html

は基本的に：

1）を使用すると、白い

2）白い四角で開始検索しているタイプのすべての正方形をマーク： - マークをその四角い黒 -markすべて（同じタイプの）隣人を灰色にしてキューの最後に置く。

3）キューの前面から灰色の四角をつかむ： ack - そのすべての白い隣人を灰色にしてキューの最後に置く。

do /キューに四角形がある間。

は黒い四角を数え、これはあなたの接続ブロブ

。注：これはinvarientと着色が作成されます。各繰り返しの後に、白い四角に隣接する黒い四角形は決して存在しない。 このアルゴリズムはO（n）で実行されます