#include <iostream>
using namespace std;

// STRUTTURE

struct Teatro{
    bool** mat; // false=libero; true=occupato
    int n_file;
    int n_posti;
};

struct elem{
    int fila;
    int posto;
    elem* pun;
};

// FUNZIONI

void inizializzaTeatro(Teatro& t, int N, int M){
    t.n_file = N<1 ? 1 : N;
    t.n_posti = M<1 ? 1 : M;
    t.mat = new bool*[t.n_file];
    for(int i=0; i<t.n_file; i++){
        t.mat[i] = new bool[t.n_posti];
    }
    for(int i=0; i<t.n_file; i++){
        for(int j=0; j<t.n_posti; j++){
            t.mat[i][j] = false;
        }
    }
}

bool prenotaPosti(Teatro& t, int f, int k){
    if(f<1||f>t.n_file){
        cerr << "Fila non valida" << endl;
        return false;
    }
    if(k<1||k>t.n_posti){
        cerr << "Numero posti non valido" << endl;
        return false;
    }
    f--;
    bool trovato = false;
    int indice;
    for(int i=0; i<=t.n_posti-k && !trovato; i++){
        trovato=true;
        indice=i;
        for(int j=0; j<k; j++){
            if(t.mat[f][i+j]){
                trovato = false;
                break;
            }
        }
    }
    if(trovato){
        for(int s=0; s<k; s++){
            t.mat[f][indice+s] = true;
        }
    }
    return trovato;
}

int liberaPosti(Teatro& t, int f){
    if(f<1||f>t.n_file){
        cerr << "Fila non valida" << endl;
        return false;
    }
    f--;
    int liberati = 0;
    for(int j=0; j<t.n_posti; j++){
        if(j%2==0 && t.mat[f][j]){
            t.mat[f][j] = false;
            liberati++;
        }
    }
    return liberati;
}

elem* listaPostiPrenotati(Teatro t){
    elem* testa = NULL;
    elem* p;
    for(int i=0; i<t.n_file; i++){
        for(int j=0; j<t.n_posti; j++){
            if(t.mat[i][j]){    // inserimento in testa
                p = new elem;
                p->fila = i+1;
                p->posto = j+1;
                p->pun = testa;
                testa = p;
            }
        }
    }
    return testa;
}

void StampaTeatro(Teatro t){
    for(int i=0; i<t.n_file; i++){
        cout << '[' << i+1 << "] ";
        for(int j=0; j<t.n_posti; j++){
            if(t.mat[i][j]){
                cout << 'X';
            }else{
                cout << 'O';
            }
        }
        cout << endl;
    }
}


int main(){

    int n=3;  // numero file
    int m=5;  // numero posti
    Teatro t;

    inizializzaTeatro(t, n, m);
    StampaTeatro(t);
    bool esito = prenotaPosti(t, 2, 2);
    esito = prenotaPosti(t, 3, 4);
    esito = prenotaPosti(t, 1, 1);
    StampaTeatro(t);
    int lib = liberaPosti(t, 3);
    StampaTeatro(t);
    cout << "Posti liberati: " << lib << endl;
    esito = prenotaPosti(t, 3, 1);
    StampaTeatro(t);
    elem* l = listaPostiPrenotati(t);

    for(elem* q=l; q!=NULL; q=q->pun){
        cout << "Fila: " << q->fila << " posto: " << q->posto;
        if(q->pun != NULL){
            cout << " --> ";
        }
    }

    return 0;
}