Submission #1243633

#TimeUsernameProblemLanguageResultExecution timeMemory
1243633BERNARB01Patkice II (COCI21_patkice2)C++20
110 / 110
804 ms61936 KiB
/** * author: BERNARD B.01 **/ #include <bits/stdc++.h> using namespace std; template <class T> using rpq = priority_queue<T, vector<T>, greater<T>>; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; vector<string> a(n); for (int i = 0; i < n; i++) { cin >> a[i]; } int si, sj, ei, ej; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (a[i][j] == 'o') { si = i; sj = j; } if (a[i][j] == 'x') { ei = i; ej = j; } } } const int di[4] = {-1, 0, 1, 0}; const int dj[4] = {0, 1, 0, -1}; const string dr = "^>v<"; auto Valid = [&](int i, int j) { return (0 <= i && i < n && 0 <= j && j < m); }; rpq<tuple<int64_t, int, int>> s; vector dist(n, vector<int64_t>(m, LLONG_MAX)); vector parent(n, vector<int>(m, -1)); dist[si][sj] = 0; s.emplace(0, si, sj); while (!s.empty()) { auto [D, i, j] = s.top(); s.pop(); if (D != dist[i][j]) { continue; } for (int k = 0; k < 4; k++) { int ni = i + di[k]; int nj = j + dj[k]; int w = int(a[i][j] != dr[k] && a[i][j] != 'o'); if (Valid(ni, nj) && D + w < dist[ni][nj]) { dist[ni][nj] = D + w; parent[ni][nj] = k; s.emplace(dist[ni][nj], ni, nj); } } } cout << dist[ei][ej] << '\n'; while (true) { int k = parent[ei][ej]; ei -= di[k]; ej -= dj[k]; if (ei == si && ej == sj) { break; } a[ei][ej] = dr[k]; } for (int i = 0; i < n; i++) { cout << a[i] << '\n'; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...