Submission #497951

#TimeUsernameProblemLanguageResultExecution timeMemory
497951abc864197532Patkice II (COCI21_patkice2)C++17
110 / 110
208 ms44032 KiB
#include <bits/stdc++.h> using namespace std; #define lli long long int #define mp make_pair #define pb push_back #define eb emplace_back #define pii pair <int, int> #define X first #define Y second #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() void abc() {cout << endl;} template <typename T, typename ...U> void abc(T a, U ...b) { cout << a << ' ', abc(b...); } template <typename T> void printv(T l, T r) { while (l != r) cout << *l << " \n"[++l == r]; } template <typename A, typename B> istream& operator >> (istream& o, pair<A, B> &a) { return o >> a.X >> a.Y; } template <typename A, typename B> ostream& operator << (ostream& o, pair<A, B> a) { return o << '(' << a.X << ", " << a.Y << ')'; } template <typename T> ostream& operator << (ostream& o, vector<T> a) { if (a.empty()) return o << "{}"; bool is = false; for (T i : a) {o << (is ? ' ' : '{'), is = true, o << i;} return o << '}'; } template <typename T> struct vv : vector <vector <T>> { vv(int n, int m, T v) : vector <vector <T>> (n, vector <T>(m, v)) {} vv() {} }; template <typename T> struct vvv : vector <vv <T>> { vvv(int n, int m, int k, T v) : vector <vv <T>> (n, vv <T>(m, k, v)) {} vvv() {} }; #ifdef Doludu #define test(args...) abc("[" + string(#args) + "]", args) #define owo freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout) #else #define test(args...) void(0) #define owo ios::sync_with_stdio(false); cin.tie(0) #endif const int mod = 1e9 + 7, N = 200005, logN = 17, K = 350, M = N * 40; int dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0}; char c[4] = {'>', '<', 'v', '^'}; int main () { owo; int n, m; cin >> n >> m; vector <string> s(n); int stx = -1, sty = -1, edx = -1, edy = -1; for (int i = 0; i < n; ++i) { cin >> s[i]; for (int j = 0; j < m; ++j) { if (s[i][j] == 'o') stx = i, sty = j; if (s[i][j] == 'x') edx = i, edy = j; } } vv <int> dis(n, m, 1 << 30), rt(n, m, -1); deque <pii> dq; dis[stx][sty] = 0; dq.emplace_back(stx, sty); while (!dq.empty()) { int x, y; tie(x, y) = dq.front(); dq.pop_front(); if (x == edx && y == edy) break; for (int k = 0; k < 4; ++k) { int nx = x + dx[k], ny = y + dy[k], w = s[x][y] != c[k]; if (s[x][y] == 'o') w = 0; if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue; if (dis[nx][ny] > dis[x][y] + w) { dis[nx][ny] = dis[x][y] + w; rt[nx][ny] = k ^ 1; if (w) dq.emplace_back(nx, ny); else dq.emplace_front(nx, ny); } } } cout << dis[edx][edy] << endl; int x = edx, y = edy; while (true) { int k = rt[x][y]; x += dx[k], y += dy[k]; if (s[x][y] == 'o') break; s[x][y] = c[k ^ 1]; } for (int i = 0; i < n; ++i) { cout << s[i] << endl; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...