| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 381975 | NONAME | Patkice II (COCI21_patkice2) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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;
}
}
}
priority_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;
}