#include <iostream>
using namespace std;


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


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 MatrizDisp {
    friend class nodo1;
    friend class nodo2;
    int nfilas;
    int ncolumnas;
    nodo1* matriz;

    private:

    nodo2* CreaColumna(int Fila, int Elemento, int Gris, nodo2* sig) {
    /* {Pre: 0 <= Fila <= nfilas - 1, 0 < Elemento.} */
        nodo2* fil = new(nodo2);
        fil->fila = Fila;
        fil->elemento = Elemento;
        fil->tono_gris = Gris;
        fil->sig2 = sig;
        return fil;
    }
    /* {Post: Devuelve un nodo2 con todos sus campos actualizados.} */


    nodo1* CreaNodo(int Fila, int Columna, int Elemento, int Gris,
                       nodo1* sig) {
    /* {Pre: 0 <= Fila <= nfilas - 1, 0 <= Columna <= ncolumnas - 1, 0 < Elemento.} */
        nodo1* col = new(nodo1);
        col->posicion = Columna;
        col->sig1 = sig;
        col->columna = CreaColumna(Fila, Elemento, Gris, NULL);
        return col;
    }
    /* {Post: Devuelve un nodo1 con todos sus campos actualizados.} */


    int cuenta_elem(nodo2* elem, int minfil) {
    /* {Pre: minfil = min(nfilas1, nfilas2).} */
        int cont = 0;
        /* cont = numero de elementos en la columna con tono_gris mayor que 20
                  hasta la posicion que hemos tratado
           elem = nodo2 a tratar (NULL si no existe)
           elem->fila = numero de fila del nodo2 a tratar (si existe)
        */
        while(elem != NULL and elem->fila < minfil) {
            if (elem->tono_gris > 20) ++cont;
            elem = elem->sig2;
        }
        return cont;
    }
    /* {Post: cont contiene la suma de el número de nodos con número de columna menor
	que mincol que tienen tono_gris > 20.} */


    int cuenta_col(nodo1* col, int mincol, int minfil) {
    /* {Pre: mincol = min(ncolumnas1, ncolumnas2), minfil = min(nfilas1, nfilas2).} */
        int cont = 0;
        /* cont = numero de elementos con tono_gris mayor que 20
                  desde el valor incial de col hasta la posicion que
                  hemos tratado
           col = nodo1 a tratar (NULL si no existe)
           col->posicion = numero de columna del nodo1 a tratar (si existe)
        */
        while(col != NULL and col->posicion < mincol) {
            cont += cuenta_elem(col->columna, minfil);
            col = col->sig1;
        }
        return cont;
    }
    /* {Post: cont contiene la suma de el número de nodos con número de fila menor
	que minfil que tienen tono_gris > 20.} */

    public:

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


    void insertar(int Fila, int Columna, int Elemento, int Gris) {
    /* {Pre: 0 <= Fila <= nfilas - 1, 0 <= Columna <= ncolumnas - 1, 0 <= Elemento} */
        if (Fila > nfilas or Columna > ncolumnas or
	    Fila <= 0 or Columna <= 0) return;
        if (Elemento == 0) {
            suprimir(Fila, Columna);
            return;
        }
        if (matriz == NULL) {
            matriz = CreaNodo(Fila, Columna, Elemento, Gris, NULL);
            return;
        }
        nodo1* act = matriz;
        nodo1* ant = NULL;

        /* { act = nodo1 a tratar, o NULL si no existe
             ant = el ultimo nodo1 tratado, (en la primera iteracion NULL,
                   ya que aun no se ha tratado ninguno)
             act->posicion = numero de columna del nodo a tratar (si existe) }
        */
        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;
            /* { act2 = nodo2 a tratar, o NULL si no existe
                 ant2 = el ultimo nodo2 tratado, (en la primera iteracion NULL,
                        ya que aun no se ha tratado ninguno)
                 act->fila = numero de fila del nodo a tratar (si existe) }
            */
            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);
                if (ant2 != NULL) ant2->sig2 = nueva2;
                else act->columna = nueva2;
            }
        }
        else {
            nodo1* nueva = CreaNodo(Fila, Columna, Elemento, Gris, act);
            if (ant != NULL) ant->sig1 = nueva;
            else matriz = nueva;
        }
    }
    /* {Post: Si Elemento es 0, suprimimos el nodo perteneciente a (Fila, Columna).
        Si elemento es diferente de 0, creamos el nodo (Fila,Columna) si éste no
        existe. Si existiese, actualizamos los valores de elemento y tono_gris.}
    */


    void suprimir(int Fila, int Columna) {
    /* {Pre: 0 <= Fila <= nfilas - 1, 0 <= Columna <= ncolumnas - 1} */
        if (Fila > nfilas or Columna > ncolumnas or
	    Fila <= 0 or Columna <= 0) return;
        nodo1* act = matriz;
        nodo1* ant = NULL;
        /* { act = nodo1 a tratar, o NULL si no existe
             ant = el ultimo nodo1 tratado, (en la primera iteracion NULL,
                   ya que aun no se ha tratado ninguno)
             act->posicion = numero de columna del nodo a tratar (si existe) }
        */
        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;
            /* { act2 = nodo2 a tratar, o NULL si no existe
                 ant2 = el ultimo nodo2 tratado, (en la primera iteracion NULL,
                        ya que aun no se ha tratado ninguno)
                 act->fila = numero de fila del nodo a tratar (si existe) }
            */
            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);
            }
        }
    }
    /* {Post: Hemos suprimido el nodo correspondiente a (Fila, Columa) si existía.} */


    void limpiar() {
    /* {Pre: -} */
        nodo1* act = matriz;
        nodo1* ant = NULL;
        /* { act = nodo1 a tratar, o NULL si no existe
             ant = el ultimo nodo1 tratado, (en la primera iteracion NULL,
                   ya que aun no se ha tratado ninguno) }
        */
        while(act != NULL) {
            bool borra = false;
            nodo2* act2 = act->columna;
            nodo2* ant2 = NULL;
            /* { act2 = nodo2 a tratar, o NULL si no existe
                 ant2 = el ultimo nodo2 tratado, (en la primera iteracion NULL,
                        ya que aun no se ha tratado ninguno) }
            */
            while(act2 != NULL) {
                if (act2->tono_gris > 224) {
                    if (ant2 != NULL) ant2->sig2 = act2->sig2;
                    else if (act2->sig2 != NULL) act->columna = act2->sig2;
                    else borra = true;
                    nodo2* auxact2;
                    auxact2 = act2;
                    act2 = act2->sig2;
                    delete(auxact2);
                }
                else {
                    ant2 = act2;
                    act2 = act2->sig2;
                }
            }
            if (borra) {
                if (ant != NULL) ant->sig1 = act->sig1;
                else matriz = act->sig1;
                nodo1 *auxact;
                auxact = act;
                act = act->sig1;
                delete(auxact);
            }
            else {
                ant = act;
                act = act->sig1;
            }
        }
    }
    /* {Post: Eliminamos de la matriz todos los nodos que tienen un valor de tono_gris
        mayor de 224.}
    */


    int compara(MatrizDisp M1) {
    /* {Pre: -} */
        int cont = 0;
        int minfil = nfilas+1;
        if (M1.nfilas < nfilas) minfil = M1.nfilas+1;
        int mincol = ncolumnas+1;
        if (M1.ncolumnas < ncolumnas) mincol = M1.ncolumnas+1;
        nodo1* col1 = matriz;
        nodo1* col2 = M1.matriz;
        /* { col1 = nodo1 a tratar de la primera matriz, o NULL si no existe
             col2 = nodo1 a tratar de la segunda matriz, o NULL si no existe
             col1->posicion = numero de columna del nodo a tratar de la primera
                              matriz (si existe)
             col1->posicion = numero de columna del nodo a tratar de la segunda
                              matriz (si existe)
             cont = numero de elementos en la intereseccion de las dos matrices
                    hasta la posicion que hemos tratado cuya diferencia de
                    tono_gris es mayor que 20 }
        */
        while(col1 != NULL and col2 != NULL and
              col1->posicion < mincol and col2->posicion < mincol) {

            if (col1->posicion == col2->posicion) {
                nodo2* elem1 = col1->columna;
                nodo2* elem2 = col2->columna;
                /* { col1 = nodo1 a tratar de la primera matriz,
                            o NULL si no existe
                     col2 = nodo1 a tratar de la segunda matriz,
                            o NULL si no existe
                     col1->fila = numero de fila del nodo a tratar de la
                                  primera matriz (si existe)
                     col1->fila = numero de fila del nodo a tratar de la
                                  segunda matriz (si existe)
                     cont = numero de elementos en la intereseccion de las dos
                            matrices hasta la posicion que hemos tratado cuya
                            diferencia de tono_gris es mayor que 20 }
                */
                while(elem1 != NULL and elem2 != NULL and
                      elem1->fila < minfil and elem2->fila < minfil) {
                    if (elem1->fila == elem2->fila) {
                        int valor = elem1->tono_gris - elem2->tono_gris;
                        if (valor < 0) valor *= -1;
                        if (valor > 20) ++cont;
                        elem1 = elem1->sig2;
                        elem2 = elem2->sig2;
                    }
                    else if (elem1->fila < elem2->fila) {
                        if (elem1->tono_gris > 20) ++cont;
                        elem1 = elem1->sig2;
                    }
                    else {
                        if (elem2->tono_gris > 20) ++cont;
                        elem2 = elem2->sig2;
                    }
                }
                cont += cuenta_elem(elem1, minfil);
                cont += cuenta_elem(elem2, minfil);
                col1 = col1->sig1;
                col2 = col2->sig1;
            }
            else if (col1->posicion < col2->posicion) {
                cont += cuenta_elem(col1->columna, minfil);
                col1 = col1->sig1;
            }
            else {
                cont += cuenta_elem(col2->columna, minfil);
                col2 = col2->sig1;
            }
        }
        cont += cuenta_col(col1, mincol, minfil);
        cont += cuenta_col(col2, mincol, minfil);
        return cont;
    }
    /* {Post: Comparamos la intersección de las 2 matrices, cont hace referencia al
        número de diferencias mayores que 20 que existen entre nodos de misma
        (Fila, Columna) en las 2 matrices.}
    */
    void escriu() {
    	cout << "============ PRINT ==========" << endl;
        nodo1 * x=matriz;
        while (x!=NULL) {
            nodo2 * pos=x->columna;
            cout << x->posicion << ": ";
            while (pos!=NULL) {
                cout << pos->fila << ","<<pos->elemento<<","<<pos->tono_gris<<"   ";
                pos=pos->sig2;
            }
            cout << endl;
            x=x->sig1;
        }
    }
};