Ciao ragazzi..ho il seguente problema:
Siano
- M una matrice di dimensione n*m,
- S una collezione di stringhe; ad ogni stringa è associato un peso p = 0.
Ogni cella di M contiene una stringa appartenente alla collezione S, e il peso di una cella è esattamente
il peso della stringa contenuta in essa.
Implementare un programma che permetta di capire quale sia la porzione di spazio più conveniente da
colonizzare, ovvero il programma deve trovare e restituire la sottomatrice M’ tale che
- M’ sia una matrice quadrata di ordine k con k > 0,
- tutte le celle di M’ contengono la stessa stringa,
- la somma dei pesi delle celle di M’ sia massima in M.
Nel caso in cui esistano due o più sottomatrici massime, la sottomatrice rappresentante la soluzione del
problema è quella più vicina al punto in alto a sinistra della matrice (ovvero quella più vicina alle
coordinate (0,0)). Se esistono due sottomatrici con la stessa distanza dal punto in alto a sinistra, si
preferisce quella più vicina al bordo superiore della matrice.
Input
La lettura dovrà avvenire da standard input.
L’input consiste in un numero i (i = 1) di test; per ogni test, il formato è il seguente:
- la prima riga contiene la parola chiave test e un numero j (separati da spazio), rappresentate l’inizio
del j-esimo test;
- la seconda riga contiene i numeri c n m, dove c è il numero di stringhe presenti, n il numero di righe
della matrice, m il numero di colonne della matrice;
- le successive c righe sono nel formato s -> p dove s rappresenta una stringa e p rappresenta il
rispettivo peso associato;
- le successive n righe sono nel formato s1 s2 … sm, ovvero un numero m di stringhe separate da uno
spazio; ogni riga con questo formato rappresenta una riga della matrice.
Questo formato vale per tutti i test. L’input termina con la stringa -1.
Output
L’output del programma deve avvenire su standard output; per ogni test, l’output deve essere nel
seguente formato:
- la prima riga contiene la parola chiave result e un numero k (separati da uno spazio), rappresentanti
il k-esimo test;
- la seconda riga ha il formato (x,y) dove x e y sono numeri, rappresentanti le coordinate del punto in
alto a sinistra della sottomatrice trovata rispetto alla matrice M;
- la terza riga contiene un numero a rappresentante la somma dei valori della sottomatrice trovata.
?
Esempio input
test 1
2 4 4
ab -> 8
de -> 3
de ab ab de
de ab ab de
de ab de de
ab ab ab de
test 2
3 8 5
deut -> 11
gld -> 3
mlby -> 5
deut gld mlby deut deut
mlby mlby mlby mlby gld
deut mlby mlby mlby mylb
deut mlby mlby mlby deut
deut deut deut gld mlby
deut deut deut mlby gld
deut gld deut mlby mlby
mlby deut gld mlby deut
-1
Esempio output
result 1
(0,1)
32
result 2
(1,1)
45
Questo è il mio codice:
#include<iostream>
#include<map>
using namespace std;
map<string,int> mappa;
int function(int i, int j, int k, string **M)
{
int somma = 0;
for(int ii = i; ii < i+k; ii++)
{
for(int jj = j; jj < j+k; jj++)
{
if(M[ii][jj] != M[i][j])
return 0;
}
}
somma += mappa[M[i][j]] * (k*k);
return somma;
}
int main()
{
string test;
int numTest;
int dimMappa;
int numRighe;
int numColonne;
string stringa;
int pesoStringa;
string separatore;
cin >> test;
if(test != "test")
return 0;
cin >> numTest;
while(test != "-1")
{
cin >> dimMappa; cin >> numRighe; cin >> numColonne;
// MAPPA
for(int i = 0; i < dimMappa; i++)
{
cin >> stringa; cin >> separatore; cin >> pesoStringa;
mappa.insert(pair<string,int>(stringa,pesoStringa));
}
// MATRICE
string **M;
M = new string*[numRighe];
for(int i = 0; i < numRighe; i++)
M[i] = new string[numColonne];
//cin.ignore();
for(int i = 0; i < numRighe; i++)
{
for(int j = 0; j < numColonne; j++)
{
cin >> M[i][j];
}
}
int indiceI = -1;
int indiceJ = -1;
int max = 0;
int result = -1;
int maxTmp = -1;
for(int i = 0; i < numRighe-1; i++)
{
for(int j = 0; j < numColonne-1; j++)
{
int l = 2;
maxTmp = function(i,j,l++,M);
//result=maxTmp;
while(maxTmp != 0 && i < numRighe-(l-1) && j < numColonne-(l-1))
{
result = function(i,j,l++,M);
if(result > maxTmp)
{
maxTmp = result;
}
}
if(maxTmp > max)
{
max = maxTmp;
indiceI = i;
indiceJ = j;
}
}
}
cout << "result " << numTest << endl;
cout << "(" << indiceI << "," << indiceJ << ")" << endl;
cout << max << endl;
//mappa.clear();
/* for(int i = 0; i < numRighe; i++)
{
delete M[i];
delete M;
}*/
cin >> test;
if(test == "-1")
return 0;
cin >> numTest;
}
return 0;
}
Funziona,solo che ci mette tantissimo, 40 secondi..a fronte del nemmeno mezzo secondo del primo..vabbe che ieri sera alla prima sottomissione dava 104 sec..perche passavo ogni volta la mappa alla funzione..Altre idee per ottimizzarlo?Grazie..