Submission #806851

#	Time	Username	Problem	Language	Result	Execution time	Memory
806851		oscar1f	Maze (JOI23_ho_t3)	C++17	100 / 100	667 ms	422176 KiB

Main

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

int nbLig,nbCol,tailleMouv,ligDeb,colDeb,ligFin,colFin,dist;
vector<pair<int,int>> adja;
vector<bool> temp;
vector<string> val;
vector<vector<bool>> dv,dejaMur;
vector<pair<int,int>> frontiere,nouv,mur;
string mot;

void propage(int lig,int col,int gratos) {
    if (lig>=1 and lig<=nbLig and col>=1 and col<=nbCol and (gratos==1 or (val[lig][col]=='.' and dv[lig][col]==false))) {
        dv[lig][col]=true;
        nouv.push_back({lig,col});
        for (auto a:adja) {
            propage(lig+a.first,col+a.second,0);
        }
    }
}

void testMur(int lig,int col) {
    if (lig>=1 and lig<=nbLig and col>=1 and col<=nbCol and dv[lig][col]==false and dejaMur[lig][col]==false) {
        dejaMur[lig][col]=true;
        mur.push_back({lig,col});
    }
}

void etend(int lig,int col,int direc,int rest) {
    if (lig>=1 and lig<=nbLig and col>=1 and col<=nbCol and dv[lig][col]==false and rest>0) {
        dv[lig][col]=true;
        mur.push_back({lig,col});
        etend(lig+adja[direc].first,col+adja[direc].second,direc,rest-1);
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    adja={{-1,0},{0,1},{1,0},{0,-1}};
    cin>>nbLig>>nbCol>>tailleMouv;
    cin>>ligDeb>>colDeb>>ligFin>>colFin;
    for (int j=0;j<=nbCol+1;j++) {
        temp.push_back(false);
    }
    for (int i=0;i<=nbLig+1;i++) {
        dv.push_back(temp);
        dejaMur.push_back(temp);
    }
    val.push_back("");
    for (int i=1;i<=nbLig;i++) {
        cin>>mot;
        val.push_back(" "+mot);
    }

    propage(ligDeb,colDeb,1);
    int lig,col,nbMur;
    while (dv[ligFin][colFin]==false) {
        frontiere=nouv;
        nouv.clear();
        mur.clear();
        for (auto s:frontiere) {
            for (auto a:adja) {
                testMur(s.first+a.first,s.second+a.second);
            }
        }
        nbMur=mur.size();
        for (int i=0;i<nbMur;i++) {
            lig=mur[i].first;
            col=mur[i].second;
            etend(lig,col-1,3,tailleMouv-1);
            etend(lig,col+1,1,tailleMouv-1);
        }
        nbMur=mur.size();
        for (int i=0;i<nbMur;i++) {
            lig=mur[i].first;
            col=mur[i].second;
            etend(lig-1,col,0,tailleMouv-1);
            etend(lig+1,col,2,tailleMouv-1);
        }
        nbMur=mur.size();
        for (int i=0;i<nbMur;i++) {
            lig=mur[i].first;
            col=mur[i].second;
            propage(lig,col,1);
        }
        /*for (auto s:nouv) {
            cout<<s.first<<" "<<s.second<<endl;
        }
        cout<<endl;*/
        dist++;
    }
    cout<<dist<<endl;
}

• Subtask 1: 8 / 8
• Subtask 2: 19 / 19
• Subtask 3: 16 / 16
• Subtask 4: 19 / 19
• Subtask 5: 5 / 5
• Subtask 6: 19 / 19
• Subtask 7: 8 / 8
• Subtask 8: 6 / 6