Problema (quale struttura dati)

di il
10 risposte

Problema (quale struttura dati)

Salve a tutti... ho un problema da risolvere (http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=8&page=show_problem&problem=545)... sono un pò in dubbio su quale struttura dati adottare per la rappresentazione della matrice di input... avevo pensato ad un grafo... qualcuno è d'accordo? mi date qualche dritta perfavofe?

10 Risposte

  • Re: Problema (quale struttura dati)

    Nessuno? non ho la minima idea di come implementare questo algoritmo.. qualcuno che mi dia una dritta perfavore?
  • Re: Problema (quale struttura dati)

    Butto giu qualche riflessione senza nessuna pretesa.

    In pratica devi fare un algoritmo che partendo da ogni lettera della tabella esplora gli adiacenti ecc. ecc.
    Ti chiedi come organizzare i dati in modo che sia possibile:
    1) Ciclare su tutti gli elementi della tabella.
    2) Dato un elemento poter accedere ai suoi adiecenti ( che al massimo sono 8 ).

    Creare una rete un cui ogni elemento ha un puntatore agli adiacenti mi sembra un casino, lo escluderei.

    Potresti create un oggetto 'Tabella' che contiene una matrice 4x4 di oggetti 'Cella'.
    Ogni 'Cella' contiene la sua lettera, le sue coordinate, e un riferimento all' oggetto tabella, una roba del tipo

    class Cell
    {
    char letter;
    int row;
    int col;
    Table* table;
    ...
    }

    class Table
    {
    int cells[4][4];
    ...
    }

    Creare una struttura del genere è piuttosto semplice.
    Ciclare su ogni elemento della matrice 4x4, non è un problema, fai un doppio for.

    La cella dovrebbe avere un un metodo che restituisce l' adiacente n-esimo (se esiste), il primo e quello di coordinate (row-1, col-1) ecc. una volta stabilito le coordinate dell' adiacente, vi puoi accedere attraverso il riferimento a table.

    Per ogni cella ne richiami il metodo 'FindWords' che esplorando gli adiacenti ti restituisce tutte le parole.

    Potrebbe andare ?
  • Re: Problema (quale struttura dati)

    Secondo me la complessità di queesto algoritmo è troppo elevata (è un progetto da implementare con la minor complessità possibile)... piuttosto, perchè ti sembra un casino la creazione di un grafo? le "lettere" sarebbero i nodi e potrei "visitarle" tramite gli algoritmi usati per le visite dei grafi... la complessità mi sembra molto più bassa, anche se avrei qualche problema ad implementare questo algoritmo...
  • Re: Problema (quale struttura dati)

    In effetti pure io non ho le idee chiarissime su quale sia la strada miglire da seguire, parlandone magari qualcosa salta fuori.

    Se vuoi costruire il grafo devi definire il Nodo, che deve contenere la lettera e 8 puntatori ai nodi adiacenti, qualcosa del genere.

    class Node
    {
    char letter;
    Node* adjacents[8];
    }

    Poi devi costruire i collegamenti. Per farlo la prima cosa che mi viene in mente è di mettere prima i Nodi vuoti (cioe con solo il valore e i puntatori a null) in una matrice 4x4 poi cicli su questa matrice e per ogni nodo, assegni gli adiacenti usando gli indici delle matrice (x-1, y-1), (x, y-1), ecc.

    La cosa che non mi piace in questa soluzione è che per fare il grafo prima devo costruire la matrice, a questo punto mi viene voglia di lavorare direttamente su di essa.
  • Re: Problema (quale struttura dati)

    Ho iniziato da circa 2 ore a implementare l algoritmo e sono fermo alla lettura del file di input... riesco a leggere il file riga per riga (funz getline()) , oppure carattere per carattere (funz get()), ma non ho capito bene come passare queste benedette lettere dal file alle matrici....
  • Re: Problema (quale struttura dati)

    Finalmente ce l ho fatta, ma come al solito sorgono altri problemi... quelllo seguente è il codice che ho usato per implementare le matrici di caratteri provenienti dal file:
    #include <iostream>
    #include <fstream>
    #include <string>    
    using namespace std;
    
    void stampaMatrici(char Mat1[][4], char Mat2[][4])
    	{
    	for(int i=0; i<4; i++)
    		{
    		for(int j=0; j<4; j++)
    			cout<<Mat1[i][j];
    		cout<<endl;
    		}
    
            cout<<endl;
    
            for(int i=0; i<4; i++)
    		{
    		for(int j=0; j<4; j++)
    			cout<<Mat2[i][j];
    		cout<<endl;			
    		}
    		cout<<"----"<<endl;
    	} 
    	
    int main() {
    
    ifstream aprifile("file.txt");
    if(!aprifile)
    	{
             cout<<"Il file non esiste!";
    	 return -1;
    	}
       
    string s;
    char Matrice1[4][4];
    char Matrice2[4][4];
    
    while(s!="#")
    	{
    	int riga=0;
    	while(riga<4)	
    		{
    		int colonna=0;
    		getline(aprifile, s);
    		int j=11;
    		for(int i=0; colonna<4; i+=2, j+=2, colonna++)
    			{
    			Matrice1[riga][colonna]=s[i];
    			Matrice2[riga][colonna]=s[j];
    			}
    		riga++;
    		}
    	stampaMatrici(Matrice1,Matrice2); //DA SOSTITUIRE CON FUNZIONE CERCAPAROLECOMUNI	
    	getline(aprifile, s);
    	}
    aprifile.close(); 
        	
    return 0;
    }
    allora, la funzione che dovrò implementare per la ricerca delle parole comuni per una coppia di matrici, verrà chiamata ogni volta che dal file si leggono una coppia di matrici appunto, e restituirà una list... per ora l ho sostituita con una funzione di stampa per vedere se le matrici vengono effettivamente lette e memorizzate (e l output risponde in modo positivo)... il problema che ora sorge è che, nella traccia del problema c'è scritto che il file deve terminare con il carattere '#' (infatti nel ciclo while più esterno c'è il controllo).. il problema è che se il file di input è del tipo:
    D F F B    W A S U
    T U G I    B R E T
    O K J M    Y A P Q
    K M B E    L O Y R
    
    Z W A V    G S F U
    U N C O    A H F T
    Y T G I    G N A L
    H G P M    B O O B
    #
    con nessuno spazio tra la fine delle matrici ed il carattere '#', allora funziona...
    se invece il file di input ha una riga vuota tra l ultima coppia di matrici ed il carattere '#' (l' input giusto dovrebbe essere di questo tipo, come è descritto sulla traccia, altrimenti il sito Uva, darà errore), l algoritmo non funziona...

    Scusate il poema, ma purtroppo non sarei riuscito a spiegarmi diversamente.... spero che qualcuno mi aiuti perchè devo finire questo progetto urgentemente... saluti...
  • Re: Problema (quale struttura dati)

    Finalmente ho risolto anche questo problema...
    
    ....
    ....
    ....
    getline(aprifile, s);
    
        while(s!="#")
    	{
    	int riga=0;
    		while(riga<4)	
    			{
    			int colonna=0;
    			int j=11;
    			for(int i=0; colonna<4; i+=2, j+=2, colonna++)
    				{
    				Matrice1[riga][colonna]=s[i];
    				Matrice2[riga][colonna]=s[j];
    				}
    			riga++;	
    			getline(aprifile, s);
    			}
    	stampaMatrici(Matrice1,Matrice2); //FUNZIONE CERCAPAROLE COMUNI	
    	getline(aprifile, s);
    	}
    .....
    .....
    .....
  • Re: Problema (quale struttura dati)

    Stavo pensando al fatto che la richiesta è di avere strutture semplici. In effetti puoi benissimo fare a meno di grafi o strutture complesse. Ti basta la matrice delle lettere e poi per passare da un elemento ai suoi adiacenti ti basta ragionare sulle sue coordinate.

    Ad esempio se l' algoritmo si trova alle coordinate (x, y) puoi raggiungere i suoi adiacenti semplicemente incrementando le coordinate. Ad esempio per ciclare su tutti gli adiacenti puoi scrivere:
    
    for(x=row-1; x<=row+1; ++x)
      for(y=col-1; x<=col+1; ++y)
        ... controllando che x non sia negativo o maggiore di 3 ecc
    
    oppure
    
    for(nextRow=max(0, row-1); nextRow<=min(3, row+1); ++nextRow)
      for(nextCol=max(0, col-1); nextCol<=min(3, col+1); ++nextCol)
    
    un algoritmo che completa le parole potrebbe essere:
    
    void Completa(parola, row, col)
    {
       if (!parola.Add(row,col)
    	 return // vuol dire che la parola contiene già l' elemento a queste coordinate o non è valido.
    
       if (parlola.Lenght == 4)
          ... ok la parola è terminata fa quello che deve e ritorna
    
        Per ogni adiacente
           Completa(parola, nextRow, nextCol)
    }
    
    La classe Parola dovrebbe essere una lista che contiene le informazioni su quali celle sono state aggiunte per evitare di inserirne un doppia.
  • Re: Problema (quale struttura dati)

    Scusa, ma non ho capito bene questo algoritmo... mi sembra un pò incasinato.. vorrei qualcosa di più semplice e strutturato... sto cercando di implementare il tutto con gli alberi binari... vedremo cosa ne uscirà fuori...
  • Re: Problema (quale struttura dati)

    Salve, sono riuscito a "trasformare" la matrice in un grafo... ho creato anche la matrice d'adiacenza che mi dice ogni nodo(lettera) a quali altri è adiacente... ora resta la parte fondamentale dell algoritmo: trovare tutte le possibili parole di 4 lettere, a partire da una lettera.... qualcno ha un idea?
Devi accedere o registrarti per scrivere nel forum
10 risposte