Comprimir matriu dispersa T69717


Statement
 

pdf   zip

Una matriu es considera dispersa si més del 70% dels seus elements són zeros.

Per tal que la matriu ocupi menys espai s’ha pensat en comprimir les matrius disperses. El format comprimit d’una matriu consisteix en una llista de tuples o triples dels elements diferents de zero de la forma: (x,y,v)(x, y, v) on:

  • x és l’índex de la fila (començant per 0).

  • y és l’índex de la columna (començant per 0).

  • v és el valor de l’element a la posició (x,y)(x, y) .

A més el primer element d’aquest llistat indica la mida de la matriu.

Suposem que tenim la matriu següent: [00300050000000170000]\begin{bmatrix} 0 & 0 & 3 & 0 & 0 \\ 0 & 5 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1\\ 7 & 0 & 0 & 0 & 0\\ \end{bmatrix}

la versió comprimida de la matriu seria:

[ <4,5,0>, <0,2,3>, <1,1,5>, <2,4,1>, <3,0,7> ]

Escriu un programa que llegeixi una seqüència de matrius d’enters no buides i faci un estudi de compressió de cada matriu. El programa ha de mostrar per cada matriu:

  1. Si la matriu donada és dispersa o no.

  2. La versió comprimida de la matriu seguint el format indicat anteriorment.

  3. El nombre d’enters que té la matriu i el nombre d’enters que ocupa la versió comprimida de la matriu.

IMPORTANT! Has d’implementar i usar la funció comprimir que, donada una matriu d’enters torna un vector amb la matriu comprimida.

void comprimir(const vector<vector<int>> &mat, vector<Casella> &compr);

El tipus Casella és el següent:

struct Casella {
	int fil;
	int col;
	int valor;
};

Entrada

L’entrada consisteix en una seqüència de matrius d’enters. Cada matriu es defineix com:

  • dos naturals indicant les dimensions de la matriu.

  • els valors de la matriu.

Sortida

Mostra per cada matriu de la seqüència les següents línies:

  • La paraula "Matriu" i el número de la matriu d’entrada seguit de ":"

  • La cadena de caràcters "DISPERSA" si la matriu és dispersa i "NO DISPERSA" si no ho és.

  • La paraula "Matriu" i el número de la matriu d’entrada seguit de " comprimida:"

  • La versió comprimida de la matriu el format de la qual es pot veure en l’exemple anterior.

  • El nombre d’enters que té la matriu i el nombre d’enters que ocupa la versió comprimida de la matriu.

Per obtenir més detalls sobre la sortida consulta els jocs de proves públics.

Public test cases

  • Input

    3 3
1 0 2
0 1 0
2 0 1

1 1
1010

15 5
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
1 2 3 4 5
2 3 4 5 1
3 4 5 1 2
4 5 1 2 3
5 1 2 3 4
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0

    Output

    Matriu 1: 
NO DISPERSA
Matriu 1 comprimida:
[ <3,3,0>, <0,0,1>, <0,2,2>, <1,1,1>, <2,0,2>, <2,2,1> ]
9 18

Matriu 2: 
NO DISPERSA
Matriu 2 comprimida:
[ <1,1,0>, <0,0,1010> ]
1 6

Matriu 3: 
NO DISPERSA
Matriu 3 comprimida:
[ <15,5,0>, <5,0,1>, <5,1,2>, <5,2,3>, <5,3,4>, <5,4,5>, <6,0,2>, <6,1,3>, <6,2,4>, <6,3,5>, <6,4,1>, <7,0,3>, <7,1,4>, <7,2,5>, <7,3,1>, <7,4,2>, <8,0,4>, <8,1,5>, <8,2,1>, <8,3,2>, <8,4,3>, <9,0,5>, <9,1,1>, <9,2,2>, <9,3,3>, <9,4,4> ]
75 78

  • Input

    3 4
0 0 0 0
0 0 0 0
0 0 0 1

10 10
1 2 3 4 5 6 7 8 9 10
2 4 6 8 10 12 14 16 18 20
3 6 9 12 15 18 21 24 27 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0

10 10
1 2 3 4 5 6 7 8 9 10
2 4 6 8 10 12 14 16 18 20
3 6 9 12 15 18 21 24 27 30
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0

4 5
1 0 0 0 0
0 5 0 0 0
0 0 8 0 0
0 0 -1 9 0

    Output

    Matriu 1: 
DISPERSA
Matriu 1 comprimida:
[ <3,4,0>, <2,3,1> ]
12 6

Matriu 2: 
DISPERSA
Matriu 2 comprimida:
[ <10,10,0>, <0,0,1>, <0,1,2>, <0,2,3>, <0,3,4>, <0,4,5>, <0,5,6>, <0,6,7>, <0,7,8>, <0,8,9>, <0,9,10>, <1,0,2>, <1,1,4>, <1,2,6>, <1,3,8>, <1,4,10>, <1,5,12>, <1,6,14>, <1,7,16>, <1,8,18>, <1,9,20>, <2,0,3>, <2,1,6>, <2,2,9>, <2,3,12>, <2,4,15>, <2,5,18>, <2,6,21>, <2,7,24>, <2,8,27> ]
100 90

Matriu 3: 
NO DISPERSA
Matriu 3 comprimida:
[ <10,10,0>, <0,0,1>, <0,1,2>, <0,2,3>, <0,3,4>, <0,4,5>, <0,5,6>, <0,6,7>, <0,7,8>, <0,8,9>, <0,9,10>, <1,0,2>, <1,1,4>, <1,2,6>, <1,3,8>, <1,4,10>, <1,5,12>, <1,6,14>, <1,7,16>, <1,8,18>, <1,9,20>, <2,0,3>, <2,1,6>, <2,2,9>, <2,3,12>, <2,4,15>, <2,5,18>, <2,6,21>, <2,7,24>, <2,8,27>, <2,9,30> ]
100 93

Matriu 4: 
DISPERSA
Matriu 4 comprimida:
[ <4,5,0>, <0,0,1>, <1,1,5>, <2,2,8>, <3,2,-1>, <3,3,9> ]
20 18
    • Information
    Author
    Bernardino Casas
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++