0

I am trying to solve the following problem:

Assume we have a 8 times 8 grid (of course it could be a larger grid).

We label all outer boundary points of the square as 'n', and points adjacent to them as 't', and all other points are 'f'.

I want to program a process that transfers all points to be 'n' by the following rule (I need to follow this rule, because this problem is a part of a bigger problem while the rest part is irrelevant to my question here):

I need to put all 't' points in order, and transfer the first element to be 'n'. Then I need to delete the first element which has been changed to 'n', and move the last element to the first location. Also, I need to relabel all 'f' points that are adjacent to the changed point as 't' and put them to the end of the sequence of 't' points. I need to continue this process until there is no 't' or 'f'.

To do this I used array with variable size, and my code is as the following:

int i,j;
char c[n+1][n+1];
int count=0;
int newi[4];
int newj[4];
int ind;
//initialization
for(i=0; i<n+1;i++){
    for(j=0;j<n+1;j++){
        if(i==0||j==0||i==n||j==n){
            c[i][j]='n';           //tagged as newly known
        }
        else if(i==1||j==1||i==n-1||j==n-1){
            c[i][j]='t';               //trial points
        }
        else{
            c[i][j]='f';               //far away points
        }
    }
}
for(i=0; i<n+1;i++){
    for(j=0;j<n+1;j++){
        if(c[i][j]=='t'){
            count=count+1;           //count is number of 't'
        }
    }
}

int ri[count]; //array that stores the row index of trial points;
int ci[count]; //array that stores the column index of trial points;
int k=0;
for(i=0; i<n+1;i++){
    for(j=0;j<n+1;j++){
        if(c[i][j]=='t'){
            ri[k]=i;
            ci[k]=j;
            k=k+1;
        }
    }
}
while(count>0){
    int num=0;
    i=ri[0];
    j=ci[0];
    c[i][j]='n';
    ri[0]=ri[count-1];
    ci[0]=ci[count-1];
    count--;
    int newcount=0;
    if(c[i-1][j]=='f'){
        c[i-1][j]='t';
        newcount++;
        newi[newcount-1]=i-1;
        newj[newcount-1]=j;
    }
    if(c[i+1][j]=='f'){
        c[i+1][j]='t';
        newcount++;
        newi[newcount-1]=i+1;
        newj[newcount-1]=j;
    }
    if(c[i][j-1]=='f'){
        c[i][j-1]='t';
        newcount++;
        newi[newcount-1]=i;
        newj[newcount-1]=j-1;
    }
    if(c[i][j+1]=='f'){
        c[i][j+1]='t';
        newcount++;
        newi[newcount-1]=i;
        newj[newcount-1]=j+1;
    }
   count=count+newcount;
    for(ind=count-newcount;ind<count;ind++)/////
    {
        ri[ind]=newi[ind-count+newcount];
        ci[ind]=newj[ind-count+newcount];
    } 
}

It works fine for several loops at the beginning. However, after my careful check, then in a loop the code

for(ind=count-newcount;ind<count;ind++)/////
    {
        ri[ind]=newi[ind-count+newcount];
        ci[ind]=newj[ind-count+newcount];
    }

not only add new elements to the end of index arrays 'ri' and 'ci', but also changed the first element of 'ri', and then mess up everything.

My question is that how this happens. Is it a problem caused by using array with variable length? Should I avoid using arrays with variable length?

Improve this question
14
  • 2
    Have you tried a debugger? Commented Jun 21, 2017 at 16:42
  • 1
    @Alex Track the indices? Why are they going out of bounds? Can be debugged very well. Commented Jun 21, 2017 at 16:45
  • 1
    You need to post a minimal reproducible example. This code does not declare n, missing #includes, missing main(); in short, uncompilable. Commented Jun 21, 2017 at 16:51
  • 1
    @Alex: Sure: trace and inspect. Commented Jun 21, 2017 at 16:57
  • 1
    @Alex: A debugger can do more than catch a segmentation fault! Commented Jun 21, 2017 at 17:13

2 Answers 2

Reset to default
3

It seems that you misinterpret the term VLA. It doesn't means that the size of the array may vary, but that you can dynamically decide what is the size of the array (but the size is fixed once).

You are adding more element to ri and ci without having reallocate them... I suggest you to, first use dynamic allocation:

int *ri = calloc(sizeof(int),count); //array that stores the row index of trial points;
if (ri==NULL) { /* error */ }
int *ci = calloc(sizeof(int),count);
if (ci==NULL) { /* error */ }

then add two lines just before your problematic loop as:

int *ri2 = realloc(ri,count*sizeof(int));
if (ri2==NULL) { /* error */ }
ri = ri2;
int *ci2 = realloc(ci,count*sizeof(int));
if (ci2==NULL) { /* error */ }
ci = ci2;

In between these portion of code, count may change!

--- EDIT ---

You need to also take care about Alex's answer...

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

calloc and realloc have different semantics. In particular, calloc() initializes the returned array with zero, realloc does not. This can lead to surprises. Also, you could maybe show how to do error checking with realloc(), the realloc statements above show exactly what one should never do.
1

Yes, that is what is causing the problem. While you still have not said what your n is, so the problem described in the other poster's answer might also be applicable; however, there are also problems within the code you posted.

When you say statements like

c[i][j+1]='t';

In case i == n, then

c[i][j+1] = c[i][n+1] = c[i+1][0]

This is because your array is n+1 x n+1, so any time you access the n+1-st entry, it spills over into the next index.

If you check whether i == n before attempting to set the value, then you would avoid this error.

Improve this answer

3 Comments

His array is (n+1)x(n+1)... char c[n+1][n+1];
Yeah, he edited the post, it looks like. Still has the same problem though... Also for accessing indices <0.
I forgot this line: # define n 7.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.