Problem with algorithm in C

Asked

Viewed 78 times

0

Good people , is the following , I am developing a project that aims to find a word in a soup of letters , the rules are as follows:

The letter can be found at any position
( East, North , South , West, Northeast , Northeast , South , South )

The word can be found backwards
( for example: 'ANA' can be found in 'AN' )

Well, it turns out my recursive algorithm doesn’t work, I wonder if anyone has any explanation for this !!
Thank you!

Code:

void caminhos(char **sopa) {
    char *palavra = "PORTO";

    char sopa2[][5]= {'P','O','Y','T','O',
                      'X','R','T','O','Y',
                      'Y','Z','C','A','S',
                      'X','Z','Y','X','A'};
    // ciclos a ser implementados

    int *referencias = procurarPalavra("PORTO", sopa2);


    imprimirReferencias(referencias,(int)strlen(palavra));


}



int *procurarPalavra(char *palavra, char sopa[][5]) {
    //esta funcao cria espaço para as referencias, chama a funcao recursiva, e retorna as referencias

    //  array de ints com as referencias dos caminhos e com tamanho de palavra
    int *referencias = (int*)calloc(strlen(palavra),sizeof(int));

    // procura na posicao (0,0) pela palavra PORTO
    procurarLetras(0,0,sopa,palavra,0,referencias);

    return referencias;

}

void procurarLetras(int row,int col, char m[][5],char *palavra,int coordenada,int *referencias) {


    // consistencia
    if( (row < 0 || col < 0) && row>4 && col>5) return;

    // (palavra) seja '\0'
    if(*palavra == '\0') {
        puts("\n Encontrei palavra na sopa :)");
        imprimirReferencias(referencias, 5);
        exit(1);
    }
    // se char for igual à palavra
    if(m[row][col] == *palavra) {
        *(referencias+1) = coordenada;
        printf("\n LETRA: %c | COORDENADA: %d",*palavra,coordenada);
        procurarLetras(row, col, m, palavra+1, coordenada, referencias);
        return;
    }




    // 1 ESTE
    procurarLetras(row, col+1, m, palavra, 1, referencias);

    // 2 SUL
    procurarLetras(row+1, col, m, palavra, 2, referencias);

    // 3 NORTE
    procurarLetras(row-1, col, m, palavra, 3, referencias);

    // 4 OESTE
    procurarLetras(row, col-1, m, palavra, 4, referencias);

    // 5 NORDESTE
    procurarLetras(row-1, col+1, m, palavra, 5, referencias);

    // 6 NORDOESTE
    procurarLetras(row-1, col-1, m, palavra, 6, referencias);

    // 7 SULDESTE
    procurarLetras(row+1, col+1, m, palavra, 7, referencias);

    // 8 SULDOESTE
    procurarLetras(row+1, col-1, m, palavra, 8, referencias);
}




void imprimirReferencias(int *referencias, int tamanho) {
    // imprime as referencias da palavra na sopa
    for(int i=0;i<tamanho;i++) {
        printf("--> %d",*(referencias+i));
    }
    puts("");
}
  • Are you sure that this test: if( (Row < 0 || col < 0) && Row>4 && col>5) Return; is correct? Shouldn’t it be OR (||)? As Row > 4 and col <= 5, for example, shall be considered valid.

  • Yes, this I had already changed to || forget to change here , however it does not work anyway , thanks !

  • Why the recursive solution? Certainly not the most natural

  • is the one that contains the least lines of code ,and also challenges me the most ..

  • Do you have any idea what it would be like iteratively?

  • Yes, iteratively it’s simpler but more extensive. As for the code there are several things that are not very clear and that make it difficult to give an answer without knowing the real objective. 1) How is called the function caminhos and what parameter passed ? 2) The initializer of the sopa2 two is incorrect and several keys are missing from it. 3) What does the returned array of references mean? Normally a location on a matrix has two coordinates, but it doesn’t seem like your code. 4) The order of functions is not correct unless you are using prototypes/statements 5) calloc is incorrect.

Show 1 more comment
No answers

Browser other questions tagged

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