Segmentation fault: branch and bound in c

5

I'm having a persistent error in my code. My goal is to find the path in a maze mounted on an array with an algorithm of type branch and bound . Here is 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 it is pointed out:

  

segmentation fault

It's as if the vector was not storing the data as it should. The lab array passed is of this type:

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

Where X corresponds to the initial position, 0 corresponds to the free paths, 1 corresponds to 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 sorted from highest to lowest priority. Home 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 am grateful for any kind of help.

    
asked by anonymous 24.02.2015 / 02:52

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), the error occurs because you try to access an element of the lab array that does not exist.

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

Similarly for width.

    
24.02.2015 / 17:52