Submission #806693

#TimeUsernameProblemLanguageResultExecution timeMemory
806693ArturgoMaze (JOI23_ho_t3)C++14
8 / 100
50 ms12128 KiB
#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} }; int curPasse = 0; vector<vector<int>> derPasse; 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) ); 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++; // expand rectangles vector<pair<int, int>> cells = murs; for(pair<int, int> cell : cells) { aExplorer.push_back(cell); terrain[cell.first][cell.second] = '.'; dansAExplorer[cell.first][cell.second] = true; } for(int iFois = 0;iFois < cote - 1;iFois++) { cells = expand(cells, deps[0]); cells = expand(cells, deps[2]); } for(int iFois = 0;iFois < cote - 1;iFois++) { cells = expand(cells, deps[1]); cells = expand(cells, deps[3]); } } cout << dist << endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...