Submission #929089

#TimeUsernameProblemLanguageResultExecution timeMemory
929089a_l_i_r_e_z_aPatkice II (COCI21_patkice2)C++17
110 / 110
209 ms60240 KiB
// In the name of God // Hope is last to die #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; #define pb push_back // #define int long long #define S second #define F first #define mp make_pair #define smax(x, y) (x) = max((x), (y)) #define smin(x, y) (x) = min((x), (y)) #define all(x) (x).begin(), (x).end() #define len(x) ((int)(x).size()) const int maxn = 2000 + 5; const int inf = 1e9 + 7; int n, m, a, b, c, d, ti[maxn][maxn], dist[maxn][maxn]; int dx[] = {0, 1, 0, -1}; int dy[] = {1, 0, -1, 0}; int par[maxn][maxn]; string s[maxn]; deque<pii> q; bool is_val(int x, int y){ return min(x, y) >= 0 && x < n && y < m; } void bfs(){ memset(dist, 63, sizeof dist); memset(par, -1, sizeof par); dist[a][b] = 0; for(int i = 0; i < 4; i++){ int xx = a + dx[i]; int yy = b + dy[i]; if(!is_val(xx, yy)) continue; dist[xx][yy] = 0; q.push_front(mp(xx, yy)); } while(q.size()){ int x = q.front().F, y = q.front().S; q.pop_front(); if(x == c && y == d) break; for(int i = 0; i < 4; i++){ int xx = x + dx[i]; int yy = y + dy[i]; if(!is_val(xx, yy)) continue; int w = (ti[x][y] != i); if(dist[xx][yy] > w + dist[x][y]){ dist[xx][yy] = w + dist[x][y]; par[xx][yy] = i; if(w) q.push_back(mp(xx, yy)); else q.push_front(mp(xx, yy)); } } } } int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> m; for(int i = 0; i < n; i++){ cin >> s[i]; for(int j = 0; j < m; j++){ if(s[i][j] == '.') ti[i][j] = 4; if(s[i][j] == '>') ti[i][j] = 0; if(s[i][j] == '<') ti[i][j] = 2; if(s[i][j] == '^') ti[i][j] = 3; if(s[i][j] == 'v') ti[i][j] = 1; if(s[i][j] == 'o'){ ti[i][j] = 5; a = i, b = j; } if(s[i][j] == 'x'){ ti[i][j] = 6; c = i, d = j; } } } bfs(); cout << dist[c][d] << '\n'; while(par[c][d] != -1){ int dir = par[c][d]; c = c - dx[dir]; d = d - dy[dir]; if(dir == 0) s[c][d] = '>'; if(dir == 1) s[c][d] = 'v'; if(dir == 2) s[c][d] = '<'; if(dir == 3) s[c][d] = '^'; } for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++) cout << s[i][j]; cout << '\n'; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...