Submission #497984

#TimeUsernameProblemLanguageResultExecution timeMemory
497984dannyboy20031204Patkice II (COCI21_patkice2)C++17
110 / 110
286 ms112240 KiB
#include <bits/stdc++.h> #define ll long long #define int long long #define fi first #define se second #define mp make_pair using namespace std; void db() {cout << endl;} template <typename T, typename ...U> void db(T a, U ...b) { //return; cout << a << ' ', db(b...); } #ifdef Cloud #define file freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout) #else #define file ios::sync_with_stdio(false); cin.tie(0) #endif const int inf = 1e9, N = 2001, mod = 1e9 + 7; bool vis[N][N]{}; int dis[N][N]{}, n, m; pair<int, int> par[N][N], st, ed; deque<pair<int, int>> q; void add(int i, int j, int a, int b, int d){ if (i < 0 or j < 0 or i >= n or j >= m) return; if (dis[a][b] + d >= dis[i][j]) return; dis[i][j] = dis[a][b] + d; par[i][j] = {a, b}; if (d) q.push_back({i, j}); else q.push_front({i, j}); } signed main(){ file; cin >> n >> m; string s[n]; for (string &i : s) cin >> i; for (int i = 0; i < n; i++){ for (int j = 0; j < m; j++){ if (s[i][j] == 'o'){ q.push_back({i, j}); vis[i][j] = true; st = {i, j}; } if (s[i][j] == 'x'){ ed = {i, j}; } dis[i][j] = inf; } } dis[st.fi][st.se] = 0; while (!q.empty()){ auto u = q.front(); q.pop_front(); if (s[u.fi][u.se] == '<') add(u.fi, u.se - 1, u.fi, u.se, 0); if (s[u.fi][u.se] == '>') add(u.fi, u.se + 1, u.fi, u.se, 0); if (s[u.fi][u.se] == '^') add(u.fi - 1, u.se, u.fi, u.se, 0); if (s[u.fi][u.se] == 'v') add(u.fi + 1, u.se, u.fi, u.se, 0); add(u.fi, u.se - 1, u.fi, u.se, 1); add(u.fi, u.se + 1, u.fi, u.se, 1); add(u.fi - 1, u.se, u.fi, u.se, 1); add(u.fi + 1, u.se, u.fi, u.se, 1); } cout << dis[ed.fi][ed.se] - 1 << '\n'; while (ed != st){ auto pre = par[ed.fi][ed.se]; if (dis[pre.fi][pre.se] != dis[ed.fi][ed.se] and pre != st){ if (ed.fi == pre.fi + 1) s[pre.fi][pre.se] = 'v'; if (ed.fi == pre.fi - 1) s[pre.fi][pre.se] = '^'; if (ed.se == pre.se + 1) s[pre.fi][pre.se] = '>'; if (ed.se == pre.se - 1) s[pre.fi][pre.se] = '<'; } ed = pre; } for (string i : s) cout << i << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...