Submission #806720

#	Time	Username	Problem	Language	Result	Execution time	Memory
806720		Arturgo	Maze (JOI23_ho_t3)	C++14	100 / 100	355 ms	132088 KiB

Main

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

pair<int, int> operator + (const pair<int, int>& a, const pair<int, int>& b) {
    return {a.first + b.first, a.second + b.second};
}

int nbLigs, nbCols, cote;
int lDeb, cDeb, lFin, cFin;
vector<string> terrain;

bool estDans(pair<int, int> p) {
   return p.first >= 0 && p.second >= 0 
   && p.first < nbLigs && p.second < nbCols;
}

vector<pair<int, int>> aExplorer;
vector<vector<bool>> explorees, dansAExplorer;

pair<int, int> deps[4] = {
    {0, 1},
    {1, 0},
    {0, -1},
    {-1, 0}
};

vector<pair<int, int>> expand(vector<pair<int, int>> cells, 
    pair<int, int> dir) {
    vector<pair<int, int>> nouvCells;
    
    for(pair<int, int> cell : cells) {
        pair<int, int> nxt = cell + dir;
        
        if(estDans(nxt)
        && !dansAExplorer[nxt.first][nxt.second]) {
            aExplorer.push_back(nxt);
            terrain[nxt.first][nxt.second] = '.';
            dansAExplorer[nxt.first][nxt.second] = true;
            
            nouvCells.push_back(nxt);
        }
    }
    
    return nouvCells;
}

int main() {
    ios_base::sync_with_stdio(false);

    cin >> nbLigs >> nbCols >> cote;
    cin >> lDeb >> cDeb >> lFin >> cFin;
    lDeb--; cDeb--; lFin--; cFin--;
    
    for(int iLig = 0;iLig < nbLigs;iLig++) {
        string lig;
        cin >> lig;
        terrain.push_back(lig);
    }
    
    explorees = vector<vector<bool>>(
        nbLigs, vector<bool>(nbCols, false)
    );
    
    dansAExplorer = vector<vector<bool>>(
        nbLigs, vector<bool>(nbCols, false)
    );
    
    dansAExplorer[lDeb][cDeb] = true;
    aExplorer.push_back({lDeb, cDeb});
    
    int dist = 0;
    while(true) {
        vector<pair<int, int>> murs;
        while(!aExplorer.empty()) {
            pair<int, int> cell = aExplorer.back();
            aExplorer.pop_back();
            
            if(terrain[cell.first][cell.second] == '#') {
                murs.push_back({cell.first, cell.second});
            }
            else {
                explorees[cell.first][cell.second] = true;
                
                for(pair<int, int> dep : deps) {
                    pair<int, int> nxt = cell + dep;
                    if(estDans(nxt) && !dansAExplorer[nxt.first][nxt.second]) {
                        dansAExplorer[nxt.first][nxt.second] = true;
                        aExplorer.push_back(nxt);
                    }
                }
            }
        }
        
        if(explorees[lFin][cFin]) {
            break;
        }
        dist++;
        
        for(pair<int, int> cell : murs) {
            aExplorer.push_back(cell);
            terrain[cell.first][cell.second] = '.';
            dansAExplorer[cell.first][cell.second] = true;
        }
  
        vector<pair<int, int>> cellsH[2] = {murs, murs};
        vector<pair<int, int>> vues = murs;
        
        for(int iFois = 0;iFois < cote - 1;iFois++) {
            cellsH[0] = expand(cellsH[0], deps[0]);
            vues.insert(vues.end(), cellsH[0].begin(), cellsH[0].end());
            
            cellsH[1] = expand(cellsH[1], deps[2]);
            vues.insert(vues.end(), cellsH[1].begin(), cellsH[1].end());
        }
        
        vector<pair<int, int>> cellsV[2] = {vues, vues};
        
        for(int iFois = 0;iFois < cote - 1;iFois++) {
            cellsV[0] = expand(cellsV[0], deps[1]);
            cellsV[1] = expand(cellsV[1], deps[3]);
        }
    }
    
    cout << dist << endl;
    return 0;
}

• 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