제출 #929065

#제출 시각아이디문제언어결과실행 시간메모리
929065Amirreza_FakhriPatkice II (COCI21_patkice2)C++17
110 / 110
796 ms300888 KiB
// In the name of the God #include <bits/stdc++.h> #define ll long long // #define int long long #define pb push_back #define F first #define S second #define mp make_pair #define pii pair <int, int> #define smin(x, y) (x) = min((x), (y)) #define smax(x, y) (x) = max((x), (y)) #define all(x) (x).begin(), (x).end() using namespace std; const int inf = 1e9+7; const int mod = 998244353; const int maxn = 2e3+5; int r, s, si, so, d[maxn*maxn], par[maxn*maxn]; char t[maxn][maxn]; vector <pii> adj[maxn*maxn]; deque <int> q; bool val(int i, int j) { return min(i ,j) >= 0 and i < r and j < s; } int id(int i, int j) { return i*maxn+j; } int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> r >> s; for (int i = 0; i < r; i++) { for (int j = 0; j < s; j++) { cin >> t[i][j]; if (t[i][j] == 'o') si = id(i, j); if (t[i][j] == 'x') so = id(i, j); int x = i+1, y = j+0, w = 1; if (val(x, y)) { if (t[i][j] == 'o' or t[i][j] == 'v') w = 0; adj[id(i, j)].pb(mp(id(x, y), w)); } x = i-1, y = j+0, w = 1; if (val(x, y)) { if (t[i][j] == 'o' or t[i][j] == '^') w = 0; adj[id(i, j)].pb(mp(id(x, y), w)); } x = i+0, y = j+1, w = 1; if (val(x, y)) { if (t[i][j] == 'o' or t[i][j] == '>') w = 0; adj[id(i, j)].pb(mp(id(x, y), w)); } x = i+0, y = j-1, w = 1; if (val(x, y)) { if (t[i][j] == 'o' or t[i][j] == '<') w = 0; adj[id(i, j)].pb(mp(id(x, y), w)); } } } memset(d, 63, sizeof d); d[si] = 0; q.push_front(si); while (q.size()) { int v = q.front(); q.pop_front(); for (pii e : adj[v]) { int u = e.F; if (d[v]+e.S < d[u]) { d[u] = d[v]+e.S; par[u] = v; if (e.S) q.push_back(u); else q.push_front(u); } } } int v = so; while (v != si) { int u = par[v]; int i = u/maxn, j = u%maxn; if (v == u+1) { if (!(t[i][j] == 'o' or t[i][j] == '>')) t[i][j] = '>'; } if (v == u-1) { if (!(t[i][j] == 'o' or t[i][j] == '<')) t[i][j] = '<'; } if (v == u+maxn) { if (!(t[i][j] == 'o' or t[i][j] == 'v')) t[i][j] = 'v'; } if (v == u-maxn) { if (!(t[i][j] == 'o' or t[i][j] == '^')) t[i][j] = '^'; } v = u; } cout << d[so] << '\n'; for (int i = 0; i < r; i++) { for (int j = 0; j < s; j++) cout << t[i][j]; cout << '\n'; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...