Segmentation fault: branch and bound in c

Asked

Viewed 179 times

5

I have a persistent error in my code. My goal is to find the way in a maze mounted on an array with an algorithm like branch and bound. Follows the code:

FILE *ent;
FILE *saida;
int NL;
int temp;
char c;
struct labirintos{
    int **lab;
};
struct labirintos *vetor;
int resolveLab(int **lab, int altura, int largura, int alturaInicial, int larguraInicial, int possibilidades);

int main() {
//declarações e abertura de arquivos
ent = fopen("ent.txt", "r"); //ent= fopen (argv[1], "r");
saida = fopen("sai.txt", "w"); //saida= fopen (argv[2], "w");

//ler arquivo de entrada e declarações
int i, j, k, largura = 0, altura = 0, larguraInicial = 0, alturaInicial = 0, possibilidades = 0;
fpos_t position;
char isCharacter;

fscanf(ent, "%d", &NL);
vetor = malloc(NL*sizeof(struct labirintos));
fprintf (saida, "%d\n", NL);
for(i = 0; i < NL; i++){
    fscanf(ent, "%d %d", &largura, &altura);
    fprintf (saida, "%d %d\n", largura, altura);
    //alocando o labirinto
    vetor[i].lab = malloc(altura*sizeof(int*));
    for(j = 0; j < altura; j++)
        vetor[i].lab[j] = malloc(largura*sizeof(int));        
    //salvando arquivo no lab
    for(k = 0; k < altura; k++){
        for(j = 0; j < largura; j++){
            fgetpos (ent, &position);
            fscanf(ent, "%c", &isCharacter);
            if(isalpha(isCharacter)){
                    vetor[i].lab[k][j] = 5;
                    fgetpos (ent, &position);
                    alturaInicial = k;
                    larguraInicial = j;
            }
            else{
                fsetpos(ent, &position);
                fscanf(ent, "%d ", &temp);
                vetor[i].lab[k][j] = temp;
                if (temp == 0)
                    possibilidades++;
            }
            fprintf(saida, "%d ", vetor[i].lab[k][j]);
            printf("%d ", vetor[i].lab[k][j]);
        }
        fprintf(saida, "\n");
        printf("\n");
    }
    printf("resultado: %d \n", resolveLab(vetor[i].lab, altura, largura, alturaInicial, larguraInicial, possibilidades));
    printf("\n");
}
fclose(ent);
fclose(saida);
return 0;
}

//funcao resolve lab
int resolveLab(int **lab, int altura, int largura, int alturaInicial, int larguraInicial, int possibilidades){
struct passo{
     int altura, largura, tentativas;
};

int j = larguraInicial, k = alturaInicial, i = 0, resolvido = 0, tentativaAtual = 0;
struct passo vetor[possibilidades*3];
if(k == 0 || k == altura || j == 0 || j == largura)
    resolvido = 1;
while(!resolvido){
    if(tentativaAtual < 4){
       if(lab[k][j+1] == 0){
            lab[k][j] = 1;
            lab[k][j+1] = 5;
            vetor[i].altura = k;
            vetor[i].largura = j++;
            vetor[i].tentativas = 1;
        }
        else if(lab[k+1][j] == 0){
            lab[k][j] = 1;
            lab[k+1][j] = 5;
            vetor[i].altura = k++;
            vetor[i].largura = j;
            vetor[i].tentativas = 2;
          }
        else if(lab[k][j-1] == 0){
            lab[k][j] = 1;
            lab[k][j-1] = 5;
            vetor[i].altura = k;
            vetor[i].largura = j--;
            vetor[i].tentativas = 3;
        }
        else if(lab[k-1][j] == 0){
            lab[k][j] = 1;
            lab[k-1][j] = 5;
            vetor[i].altura = k--;
            vetor[i].largura = j;
            vetor[i].tentativas = 4;
        }
        else
            tentativaAtual = 4;
    }
    else{
        while (i > 0 && vetor[i].tentativas > 4){
            i--;
            lab[k][j] = 1;
            k = vetor[i].altura;
            j = vetor[i].largura;
            lab[k][j] = 5;   /****** O erro ocorre aqui *******/
        }
        if (vetor[i].tentativas == 4 && i == 0)
            break;
    }
    i++;
    if(k == 0 || k == altura || j == 0 || j == largura)
        resolvido = 1;
}
return resolvido;
}

In the lines marked above is pointed out:

Segmentation fault

It’s like the vector isn’t storing the data as it should. The matrix lab past is of that kind:

1  1  1  1  1 
1  0  0  0  1
1  0  X  0  1
1  1  0  1  1

Where X corresponds to initial position, 0 corresponds to free paths, 1 matches the walls and possibilidades is the amount of free paths available.
There is also a hierarchy in the movements where: (Right) (Front) (Left) (Back), are ordered from highest to lowest priority.

ent.txt

2
5 4
1 1 1 1 1
1 0 0 0 1
1 0 X 0 1
1 1 0 1 1
3 4
1 1 1
1 X 1
1 0 1
1 1 1

I’m grateful for any help.

  • Welcome to Sopt, you could post as your main called this function ?

  • From a file example ent.txt if you can.

  • For correct reading of the file you should ignore blank spaces when reading the character: fscanf(ent, " %c", &isCharacter); but isCharacter gets spaces or newlines.

1 answer

5


        k = vetor[i].altura;
        j = vetor[i].largura;
        lab[k][j] = 5;   /****** O erro ocorre aqui *******/

If I interpreted your code correctly (I did not read it carefully) the error occurs because you try to access an element of the array lab that doesn’t exist.

If vetor[i].altura (k) is the number of elements of lab, the last element can be accessed with lab[k - 1]. The element lab[k] there is no!

Similarly for the width.

  • But the vector[i] indexes were recorded with the positions previously accessed in the lab matrix.

  • @Ariel makes a printf before and after lab[k] And you can see if that’s really the mistake.

  • for example: fprintf(stderr, "Alterando lab[%d][%d] para 5\n", k, j);

  • You were right, I was accessing an invalid element in the vector now that I fixed it, putting a --i; before the access, everything is perfect hahahah. Thank you very much!

Browser other questions tagged

You are not signed in. Login or sign up in order to post.