재귀를 사용하여 1을 만났을 때의 분할

Question

무어의 이웃과 같은 모든 이웃을 확인하고 무어의 이웃을 사용하여 연결된 모든 1에 대해 무작위로 생성 된 배열을 확인하기 위해 재귀를 사용해야합니다. 내 재귀 코드는 0을 만나면 잘 작동하는 것처럼 보이지만, 하나가 만났을 때 세그먼트 오류가 발생합니다. 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

재귀가 끝나지 않고 프로그램이 실패하기 때문에 stackoverflow가 발생합니다. 예를 들어, 6x6의 경우 ... (4,4), (5,5), (4,4), (5,5) ...를 recursive 번으로 호출하여 스택을 끊습니다.

free(arrStorage) 
free(arr) 

같은

또한

, free 모두 포인터의 libc/커널이 작업을 수행하는 방법에 free(a[i])

Answer 2

정말 좋은 방법을 알고하지 않기 때문에 (즉, 당신이 큐를 구축 할 수 있기 때문에 최적화가 용이 재귀를 사용하는 대신)는 3 색 알고리즘을 사용하는 것입니다.

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

는 기본적 :

1)는 흰색

2) 흰색 사각형에 시작 검색하는 유형의 모든 사각형을 표시 : - 마크가 검은 색 사각형 마가 복음의 모든 그 이웃들 (같은 타입의) 회색을 큐 끝에 넣는다.

3) 큐 앞에있는 회색 사각형을 잡아라 : ack -mark의 모든 흰색 이웃을 회색으로 표시하고 큐 끝에 넣습니다.

do/대기열에 사각형이있는 동안.

는 검은 색 사각형을 계산,이 연결된 방울

주 : 이것은 invarient와 색상을 만듭니다. 매 반복 후에는 흰색 정사각형 옆에 검은 색 사각형이 표시되지 않습니다. 이 알고리즘은 O (n)에서 실행됩니다.