#include <iostream>
using namespace std;


class nodo1 {
    friend class nodo2;
    friend class MatrizDisp;
    int posicion;
    nodo2* columna; /* puntero a la lista que cuelga de este nodo y
                        almacena los valores no nulos de la columna posicion */
    nodo1* sig1;
};


class nodo2 {
    friend class MatrizDisp;
    int elemento; /* valor en la matriz */
    int tono_gris;
    int fila;
    nodo2* sig2;
};


class MatrizDisp {
    friend class nodo1;
    friend class nodo2;
    int nfilas;
    int ncolumnas;
    nodo1* matriz;

    private:

    nodo2* CreaColumna(int Fila, int Elemento, int Gris, nodo2* sig) {
        nodo2* fil = new(nodo2);
        fil->fila = Fila;
        fil->elemento = Elemento;
        fil->tono_gris = Gris;
        fil->sig2 = sig;
        return fil;
    }


    nodo1* CreaNodo(int Fila, int Columna, int Elemento, int Gris,
                       nodo1* sig) {
        nodo1* col = new(nodo1);
        col->posicion = Columna;
        col->sig1 = sig;
        col->columna = CreaColumna(Fila, Elemento, Gris, NULL);
        return col;
    }


    public:

    MatrizDisp(int Filas, int Columnas) {
        nfilas = Filas;
        ncolumnas = Columnas;
        matriz = NULL;
    }


    void insertar(int Fila, int Columna, int Elemento, int Gris) {
        if (Elemento == 0) return;
        if (matriz == NULL) {
            matriz = CreaNodo(Fila, Columna, Elemento, Gris, NULL);
        }
        else {
            nodo1* act = matriz;
            nodo1* ant = NULL;
            while(act != NULL and act->posicion < Columna) {
                ant = act;
                act = act->sig1;
            }
            if (act!=NULL and act->posicion==Columna) {
                nodo2* act2 = act->columna;
                nodo2* ant2 = NULL;
                while(act2 != NULL and act2->fila < Fila) {
                    ant2 = act2;
                    act2 = act2->sig2;
                }
                if (act2!=NULL and act2->fila==Fila) {
                    act2->elemento = Elemento;
                    act2->tono_gris = Gris;
                }
                else {
                    nodo2* nueva2 = CreaColumna(Fila, Elemento, Gris, act2);
                    ant2->sig2 = nueva2;
                }
            }
            else {
                nodo1* nueva = CreaNodo(Fila, Columna, Elemento, Gris, act);
                ant->sig1 = nueva;
            }
        }
    }


    void suprimir(int Fila, int Columna) {
        if (matriz != NULL) {
            nodo1* act = matriz;
            nodo1* ant = NULL;
            while(act != NULL and act->posicion < Columna) {
                ant = act;
                act = act->sig1;
            }
            if (act!=NULL and act->posicion==Columna) {
                nodo2* act2 = act->columna;
                nodo2* ant2 = NULL;
                while(act2 != NULL and act2->fila < Fila) {
                    ant2 = act2;
                    act2 = act2->sig2;
                }
                if (act2!=NULL and act2->fila==Fila) {
                    if (ant2 != NULL) ant2->sig2 = act2->sig2;
                    else if (act2->sig2 != NULL) act->columna = act2->sig2;
                    else {
                        if (ant != NULL) ant->sig1 = act->sig1;
                        else matriz = act->sig1;
                        delete(act);
                    }
                    delete(act2);
                }
            }
        }
    }


    void limpiar() {
        if (matriz != NULL) {
            nodo1* act = matriz;
            nodo1* ant = NULL;
            while(act != NULL) {
                ant = act;
                act = act->sig1;

                nodo2* act2 = act->columna;
                nodo2* ant2 = NULL;
                while(act2 != NULL) {
                    if (act2->tono_gris < 20) {
                        nodo2* auxsig2 = act2->sig2;
                        if (ant2 != NULL) ant2->sig2 = act2->sig2;
                        else if (act2->sig2 != NULL) act->columna = act2->sig2;
                        else {
                            nodo1* auxsig1 = act->sig1;
                            if (ant != NULL) ant->sig1 = act->sig1;
                            else matriz = act->sig1;
                            act = auxsig1;
                            delete(act);
                        }
                        act2 = auxsig2;
                        delete(act2);
                    }
                    else {
                        act2 = act2->sig2;
                        ant2 = act2;
                    }
                }
            }
        }
    }


    int compara(MatrizDisp M1) {

    }
};