Matrius esparses (1): conversió Y29996

Una matriu esparsa (o dispersa) és una matriu en la qual la majoria dels elements són zero. En lloc d’emmagatzemar tots els elements, la representació esparsa guarda només els elements no nuls juntament amb les seves posicions, estalviant memòria i temps de còmput. Per exemple, la matriu:

$$\begin{pmatrix} 0 & 3 & 0 & 0 \\ 0 & 0 & 5 & 0 \\ 1 & 0 & 0 & 7 \end{pmatrix}$$

en representació esparsa per files queda:

on cada parella (col,val) indica la columna i el valor de cada element no nul, i el punt final . marca el final de la fila (fins i tot quan la fila és buida).

En aquest problema, representem una matriu d’enters amb el tipus Matriu i la versió esparsa amb el tipus MatriuEsparsa, definits a matrius.hh:

typedef vector<vector<int>> Matriu;

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 Converteix una Matriu en una MatriuEsparsa.
 *
 * @param M Matriu rectangular de mida n x m.
 *
 * @pre M pot ser qualsevol matriu rectangular (incloent buida).
 * @post Retorna una nova MatriuEsparsa S, amb S.ncols == m i S.files.size() == n,
 *       on S.files[i] conté, ordenades per columna ascendentment, les caselles
 *       {pos, valor} dels elements no nuls de la fila i de M.
 */
MatriuEsparsa matriu_converteix_a_esparsa(const Matriu& M);

Observació

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

Cal enviar únicament la implementació de la funció matriu_converteix_a_esparsa, incloent-hi l’include de matrius.hh. No cal enviar el main.

Entrada

La primera línia conté dos enters $n$ i $m$ ($0 \leq n, m \leq 1000$), el nombre de files i columnes de la matriu. A continuació hi ha $n$ línies, cadascuna amb $m$ enters separats per espais que representen les files de la matriu.

Sortida

La primera línia conté dos enters $n$ i $m$, les dimensions de la matriu esparsa resultant. A continuació hi ha $n$ línies, cadascuna amb les caselles no nul·les de la fila, en ordre ascendent de columna, amb el format (col,val) separades per espais, seguides d’un punt .. Les files sense cap element no nul es mostren únicament amb el punt ..