Salve, ho una matrice di caratteri in cui devo trovare tutte le parole di 4 lettere adiacenti(anche con un angolo in comune sono considerate adiacenti) che si possono formare... ES:
A S S D
S B E Y
G F O I
H U U K
ASGU SABO FOIK FEBS SYDE HUFO
mi basterebbe un algoritmo che cerchi tutte le parole di 4 lettere a partire da una lettera, così potrei ciclare l algoritmo stesso per ogni lettera della matrice....
fino ad ora non sono riuscito ad implementare un algoritmo decente... ho scelto una strada secondo me molto complicata: ho "trasformato" la matrice in un "grafo", "numerando" tutte le lettere che sono state quindi convertite in NODI... ho quindi la matrice delle adiacenze che mi dice tutte le lettere adiacenti ad una lettera... ho creato una piccola funzione all interno della classe che restituisce il primo nodo adiacente ad un nodo, se ce ne sono di non visitati.. altrimenti restituisce -1 se tutti i nodi adiacenti sono stati visitati.. per fare ciò mi sono servito di un array di bool e una funzione che imposta i nodi come visitati/non visitati... questo è il codice che ho sviluppato fino ad ora anche se non mi convince molto... qualcuno ha qualche idea migliore, oppure riesce ad implementare la funzione mancante?
struct Nodo //PER OGNI NODO ABBIAMO LA RIGA E COLONNA CORRISPONENTE ALLA MATRICE INIZIALE
{
int r;
int c;
};
class MatriceAd //CLASSE CONTENENTE LA MATRICE D'ADIACENZA CREATA CON IL COSTRUTTORE
{
private:
bool M[16][16];
bool visitati[16];
public:
MatriceAd()
{
for(int i=0; i<16; i++)
for(int j=0; j<16; j++)
M[i][j]=false;
int num=0;
for(int i=0; i<4; i++)
for(int j=0; j<4; j++, num++)
{
if(i-1>=0)
{
M[num][num-4]=true;
if(j-1>=0)
M[num][num-5]=true;
if(j+1<4)
M[num][num-3]=true;
}
if(j-1>=0)
M[num][num-1]=true;
if(j+1<4)
M[num][num+1]=true;
if(i+1<4)
{
M[num][num+4]=true;
if(j-1>=0)
M[num][num+3]=true;
if(j+1<4)
M[num][num+5]=true;
}
}
}
int primoAd(int i)
{
for(int j=0; j<16; j++)
if(M[i][j]==1 && visitati[j]==false)
return j;
return -1;
}
void visitato(int i, bool b) {visitati[i]=b;}
void svuota() {for(int i=0; i<16; i++) visitati[i]=false;}
};
void parole(int, vector<Nodo>, char[][4], MatriceAd);
int main()
{
MatriceAd m;
char Matrice[4][4] = {{'D','F','F','B'},
{'T','U','G','I'},
{'O','K','J','M'},
{'K','M','B','E'}};
vector<Nodo> nodi; //VETTORE DEI NODI
Nodo n;
for(int i=0; i<4; i++)
for(int j=0; j<4; j++)
{
n.r=i;
n.c=j;
nodi.push_back(n);
}
for(int i=0; i<16; i++) //CICLO LA FUNZIONE SEGUENTE PER OGNI NODO i
parole(i, nodi, Matrice, m); //FUNZIONE DA IMPLEMENTARE
}
void parole(int i, vector<Nodo> nodi, char Matrice[4][4], MatriceAd m)
{
}