Submission #381974

#TimeUsernameProblemLanguageResultExecution timeMemory
381974NONAMEPatkice II (COCI21_patkice2)C++17
30 / 110
2078 ms70348 KiB
#include <bits/stdc++.h> using namespace std; mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count()); template <typename T> inline bool chmin(T& a, const T b) {a = min(a, b); return (a == b);} template <typename T> inline bool chmax(T& a, const T b) {a = max(a, b); return (a == b);} const int steps[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}}; const int man = (int)(2e3 + 10); int n, m, sx, sy, ex, ey; int a[man][man], d[man][man]; array <int, 3> pr[man][man]; inline void cls() {} void solve() { cls(); string st = ".v>^<ox"; cin >> n >> m; for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { d[i][j] = 1e9; pr[i][j] = {-1, -1, -1}; char c; cin >> c; if (c == '.') { a[i][j] = 0; } if (c == 'v') { a[i][j] = 1; } if (c == '>') { a[i][j] = 2; } if (c == '^') { a[i][j] = 3; } if (c == '<') { a[i][j] = 4; } if (c == 'o') { a[i][j] = 5; sx = i, sy = j; } if (c == 'x') { a[i][j] = 6; ex = i, ey = j; } } } queue <array <int, 3> > q; q.push({0, sx, sy}); d[sx][sy] = 0; while (!q.empty()) { auto cur = q.front(); q.pop(); int c = -cur[0], x = cur[1], y = cur[2]; if (a[x][y] == 6) { continue; } if (c != d[x][y]) { continue; } if ((x == sx) && (y == sy)) { for (int i = 0; i < 4; ++i) { int cx = x + steps[i][0]; int cy = y + steps[i][1]; if ((cx >= 0) && (cx < n) && (cy >= 0) && (cy < m)) { d[cx][cy] = 0; pr[cx][cy] = {x, y, i + 1}; q.push({0, cx, cy}); } } } else { for (int i = 0; i < 4; ++i) { int cx = x + steps[i][0]; int cy = y + steps[i][1]; if ((cx >= 0) && (cx < n) && (cy >= 0) && (cy < m) && ((c + ((i + 1) != a[x][y])) < d[cx][cy])) { d[cx][cy] = c + ((i + 1) != a[x][y]); pr[cx][cy] = {x, y, i + 1}; q.push({-d[cx][cy], cx, cy}); } } } } int x = ex, y = ey, tp = -1; while ((x != sx) || (y != sy)) { if (tp != -1) { a[x][y] = tp; } int ox = x, oy = y; x = pr[ox][oy][0]; y = pr[ox][oy][1]; tp = pr[ox][oy][2]; } cout << d[ex][ey] << "\n"; for (int i = 0; i < n; ++i, cout << "\n") { for (int j = 0; j < m; ++j) { cout << st[a[i][j]]; } } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t = 1; #ifdef _LOCAL system("color a"); freopen("in.txt", "r", stdin); cin >> t; #endif for (int i = 1; i <= t; ++i) { cerr << "Case #" << i << ": \n"; solve(); cerr << "\n"; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...