Submission #850730

#	Time	Username	Problem	Language	Result	Execution time	Memory
850730		oscar1f	Furniture (JOI20_furniture)	C++17	100 / 100	237 ms	28060 KiB

furniture

#include<bits/stdc++.h>
using namespace std;

const int TAILLE_MAX=1005;
int nbLig,nbCol,nbReq,ligNouv,colNouv;
int val[TAILLE_MAX][TAILLE_MAX];
int dvDeb[TAILLE_MAX][TAILLE_MAX],dvFin[TAILLE_MAX][TAILLE_MAX];
int acces[TAILLE_MAX][TAILLE_MAX];
int nbBon[2*TAILLE_MAX];

void DFS_deb(int lig,int col) {
    if (lig<=nbLig and col<=nbCol and dvDeb[lig][col]==0 and val[lig][col]==0) {
        dvDeb[lig][col]=1;
        DFS_deb(lig+1,col);
        DFS_deb(lig,col+1);
    }
}

void DFS_fin(int lig,int col) {
    if (lig>0 and col>0 and dvFin[lig][col]==0 and val[lig][col]==0) {
        dvFin[lig][col]=1;
        DFS_fin(lig-1,col);
        DFS_fin(lig,col-1);
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>nbLig>>nbCol;
    for (int i=1;i<=nbLig;i++) {
        for (int j=1;j<=nbCol;j++) {
            cin>>val[i][j];
        }
    }
    DFS_deb(1,1);
    DFS_fin(nbLig,nbCol);
    for (int i=1;i<=nbLig;i++) {
        for (int j=1;j<=nbCol;j++) {
            if (dvDeb[i][j]==1 and dvFin[i][j]==1) {
                acces[i][j]=1;
                nbBon[i+j]++;
            }
        }
    }
    deque<pair<int,int>> enCours;
    int lig,col,longueur;
    cin>>nbReq;
    for (int ireq=0;ireq<nbReq;ireq++) {
        cin>>ligNouv>>colNouv;
        if (acces[ligNouv][colNouv]==0) {
            cout<<1<<"\n";
        }
        else if (nbBon[ligNouv+colNouv]==1) {
            cout<<0<<"\n";
        }
        else {
            cout<<1<<"\n";
            nbBon[ligNouv+colNouv]--;
            acces[ligNouv][colNouv]=0;
            enCours.push_back({ligNouv+1,colNouv});
            enCours.push_back({ligNouv,colNouv+1});
            while (!enCours.empty()) {
                longueur=enCours.size();
                for (int i=0;i<longueur;i++) {
                    lig=enCours.front().first;
                    col=enCours.front().second;
                    enCours.pop_front();
                    if (lig<=nbLig and col<=nbCol and acces[lig][col]==1 and acces[lig-1][col]==0 and acces[lig][col-1]==0) {
                        acces[lig][col]=0;
                        nbBon[lig+col]--;
                        enCours.push_back({lig+1,col});
                        enCours.push_back({lig,col+1});
                    } 
                }
            }
            enCours.push_back({ligNouv-1,colNouv});
            enCours.push_back({ligNouv,colNouv-1});
            while (!enCours.empty()) {
                longueur=enCours.size();
                for (int i=0;i<longueur;i++) {
                    lig=enCours.front().first;
                    col=enCours.front().second;
                    enCours.pop_front();
                    if (lig>0 and col>0 and acces[lig][col]==1 and acces[lig+1][col]==0 and acces[lig][col+1]==0) {
                        acces[lig][col]=0;
                        nbBon[lig+col]--;
                        enCours.push_back({lig-1,col});
                        enCours.push_back({lig,col-1});
                    } 
                }
            }
        }
    }
    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 95 / 95