Submission #1075668

#	Time	Username	Problem	Language	Result	Execution time	Memory
1075668		oscar1f	Toy (CEOI24_toy)	C++17	100 / 100	238 ms	304512 KiB

Main

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

#define int long long

const int TAILLE_MAX=1500+5;
int nbCol,nbLig,tailleHori,tailleVerti,colDebHori,ligDebHori,colDebVerti,ligDebVerti,objLig,objCol;
char grille[TAILLE_MAX][TAILLE_MAX];
int gauche[TAILLE_MAX][TAILLE_MAX],droite[TAILLE_MAX][TAILLE_MAX],haut[TAILLE_MAX][TAILLE_MAX],bas[TAILLE_MAX][TAILLE_MAX];
int dv[TAILLE_MAX][TAILLE_MAX];

void DFS(int lig,int col) {
    if (dv[lig][col]==0) {
        //cout<<lig<<" "<<col<<endl;
        dv[lig][col]=1;

        if (col<nbCol and min(bas[lig][col],bas[lig][col+1])-max(haut[lig][col],haut[lig][col+1])>tailleVerti) {
            //cout<<"droite "<<lig<<" "<<col<<endl;
            DFS(lig,col+1); //droite
        }
        if (col>1 and min(bas[lig][col],bas[lig][col-1])-max(haut[lig][col],haut[lig][col-1])>tailleVerti) {
            //cout<<"gauche "<<lig<<" "<<col<<endl;
            DFS(lig,col-1); //gauche
        }
        if (lig<nbLig and min(droite[lig][col],droite[lig+1][col])-max(gauche[lig][col],gauche[lig+1][col])>tailleHori) {
            //cout<<"bas "<<lig<<" "<<col<<endl;
            DFS(lig+1,col); //bas
        }
        if (lig<nbLig and min(droite[lig][col],droite[lig-1][col])-max(gauche[lig][col],gauche[lig-1][col])>tailleHori) {
            //cout<<"haut "<<lig<<" "<<col<<endl;
            DFS(lig-1,col); //haut
        }
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>nbCol>>nbLig>>tailleHori>>tailleVerti;
    cin>>colDebHori>>ligDebHori>>colDebVerti>>ligDebVerti;
    for (int i=1;i<=nbLig;i++) {
        for (int j=1;j<=nbCol;j++) {
            cin>>grille[i][j];
            if (grille[i][j]=='*') {
                objLig=i;
                objCol=j;
                grille[i][j]='.';
            }
        }
    }

    for (int i=1;i<=nbLig;i++) {
        for (int j=1;j<=nbCol;j++) {
            if (grille[i][j]=='.') {
                gauche[i][j]=gauche[i][j-1];
                haut[i][j]=haut[i-1][j];
            }
            else {
                gauche[i][j]=j;
                haut[i][j]=i;
            }
        }
    }
    for (int i=1;i<=nbLig;i++) {
        droite[i][nbCol+1]=nbCol+1;
    }
    for (int j=1;j<=nbCol;j++) {
        bas[nbLig+1][j]=nbLig+1;
    }
    for (int i=nbLig;i>=1;i--) {
        for (int j=nbCol;j>=1;j--) {
            if (grille[i][j]=='.') {
                droite[i][j]=droite[i][j+1];
                bas[i][j]=bas[i+1][j];
            }   
            else {
                droite[i][j]=j;
                bas[i][j]=i;
            }
        }
    }
    
    /*for (int i=1;i<=nbLig;i++) {
        for (int j=1;j<=nbCol;j++) {
            cout<<bas[i][j]<<" ";
        }
        cout<<endl;
    }*/

    DFS(ligDebHori+1,colDebVerti+1);
    if (dv[objLig][objCol]==1) {
        cout<<"YES"<<endl;
    }
    else {
        cout<<"NO"<<endl;
    }
    return 0;
}
  

• Subtask 0: 0 / 0
• Subtask 1: 14 / 14
• Subtask 2: 21 / 21
• Subtask 3: 9 / 9
• Subtask 4: 29 / 29
• Subtask 5: 27 / 27