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.
– anonimo
Yes, this I had already changed to || forget to change here , however it does not work anyway , thanks !
– David Capela
Why the recursive solution? Certainly not the most natural
– Isac
is the one that contains the least lines of code ,and also challenges me the most ..
– David Capela
Do you have any idea what it would be like iteratively?
– David Capela
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 thesopa2
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.– Isac