Submission #1244210

#TimeUsernameProblemLanguageResultExecution timeMemory
1244210BERNARB01Patkice II (COCI21_patkice2)C++20
110 / 110
170 ms40408 KiB
/** * author: BERNARD B.01 **/ #include <bits/stdc++.h> using namespace std; 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 = 0, sj = 0, ei = 0, ej = 0; 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); }; const int inf = int(1e9) + 9; vector dist(n, vector<int>(m, inf)); vector parent(n, vector<int>(m, -1)); deque<pair<int, int>> s; dist[si][sj] = 0; s.emplace_back(si, sj); while (!s.empty()) { auto [i, j] = s.front(); s.pop_front(); 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) && dist[i][j] + w < dist[ni][nj]) { dist[ni][nj] = dist[i][j] + w; parent[ni][nj] = k; if (w == 0) { s.emplace_front(ni, nj); } else { s.emplace_back(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...