Matrius esparses (3): suma T33423

Tal com vam veure al problema Matrius esparses (1): conversió, una matriu esparsa només emmagatzema els elements no nuls. Els tipus usats (definits a matrius.hh) són els mateixos:

struct Casella {
    int pos;    // índex de columna
    int valor;  // valor de l'element
};

struct MatriuEsparsa {
    int ncols;                   // nombre de columnes
    vector<list<Casella>> files; // files de la matriu esparsa
};

Fes la funció següent:

/**
* @brief Calcula la suma de dues MatriuEsparsa.
*
* @param A MatriuEsparsa de A.files.size() files i A.ncols columnes.
* @param B MatriuEsparsa de B.files.size() files i B.ncols columnes.
*
* @pre A i B són matrius esparses correctes. Les dimensions d'A i B són iguals.
*
* @post Retorna una nova MatriuEsparsa C on C.files[i] és la suma de
*       A.files[i] i B.files[i], conservant només els elements no nuls,
*       ordenats per columna ascendentment.
*/
MatriuEsparsa suma_matrius_esparses(const MatriuEsparsa& A, 
                                    const MatriuEsparsa& B);

Per verificar la precondició sobre les dimensions, cal usar el assert de assert.hh de la forma:

assert(condicio, "suma_matrius_esparses: dimensions diferents!");

Observació

Els fitxers públics (icona del gatet) contenen:

Cal enviar únicament la implementació de la funció suma_matrius_esparses en un fitxer verb|.cc|, posant els includes de matrius.hh i assert.hh. El Jutge copia el fitxer enviat en una carpeta com la proporcionada i compila fent make.

Entrada

L’entrada conté dues matrius esparses seguides. Cada matriu comença amb una línia amb dos enters $n$ i $m$ ($0 \leq n, m \leq 1000$), el nombre de files i columnes. A continuació hi ha $n$ línies, cadascuna amb les caselles no nul·les de la fila com a parelles (col,val) separades per espais, seguides d’un punt .. Les files sense elements no nuls es representen com ..

Sortida

Si les dues matrius tenen les mateixes dimensions, s’imprimeix la matriu suma en el mateix format que l’entrada: la primera línia conté les dimensions $n \times m$, seguida de $n$ línies amb les caselles no nul·les de cada fila, seguides d’un punt ..

Si les dimensions no coincideixen, s’imprimeix: suma_matrius_esparses: dimensions diferents!