Submission #1242005

#TimeUsernameProblemLanguageResultExecution timeMemory
1242005GeforgsMaze (JOI23_ho_t3)C++20
100 / 100
484 ms147176 KiB
#include <array> #include <climits> #include <iostream> #include <queue> #include <vector> using namespace std; int main(){ cin.tie(nullptr); ios::sync_with_stdio(false); int R, C, K, Sr, Sc, Gr, Gc; cin >> R >> C >> K >> Sr >> Sc >> Gr >> Gc; K = 1 - K; Sr--; Sc--; Gr--; Gc--; vector<string> A(R); for(string& a : A) { cin >> a; for(char& c : a) c = c == '#'; } // {гЃ“гЃ“гЃ«иѕїг‚ЉзќЂгЃЏгЃѕгЃ§гЃ«еї…и¦ЃгЃЄеЎ—г‚ЉгЃ¤гЃ¶гЃ—е›ћж•°, жњЂеѕЊгЃ®еЎ—г‚ЉгЃ¤гЃ¶гЃ—гЃ«г‚€гЃЈгЃ¦иЎЊгЃ‘г‚‹зё¦гЃ®з§»е‹•й‡Џ, жњЂеѕЊгЃ®еЎ—г‚ЉгЃ¤гЃ¶гЃ—гЃ«г‚€гЃЈгЃ¦иЎЊгЃ‘г‚‹жЁЄгЃ®з§»е‹•й‡Џ} г‚’жЊЃгЃ¤ // 各レイヤー 3 гѓ•г‚§гѓјг‚єгЃ® BFS // 1. 4 ж–№еђ‘гЃ« 白なら移動 / 黒なら (K - 1, K - 1) гЃ§еЎ—г‚ЉгЃ¤гЃ¶гЃ—иїЅеЉ // 2. жЁЄж–№еђ‘гЃ«з§»е‹• // 3. зё¦ж–№еђ‘гЃ«з§»е‹• vector cost(R, vector(C, array{INT_MAX, 0, 0})); vector<pair<int, int>> q1, q2; auto push = [&](vector<pair<int, int>>& q, int r, int c, int x, int y, int z) -> void { if(r < 0 || r >= R || c < 0 || c >= C) return; if(cost[r][c][0] <= x) return; cost[r][c] = {x, y, z}; q.emplace_back(r, c); }; auto push2 = [&](int r, int c, int x) -> void { if(r < 0 || r >= R || c < 0 || c >= C) return; if(A[r][c]) push(q2, r, c, x + 1, K, K); else push(q1, r, c, x, 0, 0); }; push(q1, Sr, Sc, 0, 0, 0); while(q1.size()) { // жЁЄж–№еђ‘гЃ«з§»е‹• for(int i = 0; i < q1.size(); i++) { const auto [r, c] = q1[i]; const auto [x, y, z] = cost[r][c]; if(z == 0) continue; push(q1, r, c - 1, x, y, z + 1); push(q1, r, c + 1, x, y, z + 1); } // зё¦ж–№еђ‘гЃ«з§»е‹• for(int i = 0; i < q1.size(); i++) { const auto [r, c] = q1[i]; const auto [x, y, z] = cost[r][c]; if(y == 0) continue; push(q1, r - 1, c, x, y + 1, z); push(q1, r + 1, c, x, y + 1, z); } // BFS for(int i = 0; i < q1.size(); i++) { const auto [r, c] = q1[i]; const auto [x, y, z] = cost[r][c]; push2(r - 1, c, x); push2(r + 1, c, x); push2(r, c - 1, x); push2(r, c + 1, x); } swap(q1, q2); q2.clear(); } cout << cost[Gr][Gc][0] << endl; }
#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...