Well folks, this is the following, I'm developing a project that wants to find a word in a font soup, the rules are as follows:
The letter can be found anywhere in (East, North, South, West, Northeast, North West, South West, South West)
The word can be found from back to front
(for example: 'ANA' can be found in 'AN')
Well, it turns out that my recursive algorithm does not work, I wonder if anyone has any explanation for it !! Thanks!
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 '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 '%pre%'
if(*palavra == '%pre%') {
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("");
}
'
if(*palavra == '%pre%') {
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("");
}