Submission #873092

#TimeUsernameProblemLanguageResultExecution timeMemory
873092kh0iPatkice II (COCI21_patkice2)C++17
110 / 110
891 ms392612 KiB
/** * author: kh0i * created: 18.08.2022 20:41:18 **/ #include "bits/stdc++.h" using namespace std; #ifdef LOCAL #include "debug.h" #else #define debug(...) #endif using ll = long long; const int N = 2e3 + 5; int r, s, d[N][N], vis[N][N]; pair<int, int> st, en; char a[N][N]; vector<pair<pair<int, int>, int>> adj[N][N]; pair<int, int> trace[N][N]; void solve(){ cin >> r >> s; for(int i = 1; i <= r; ++i){ for(int j = 1; j <= s; ++j){ cin >> a[i][j]; if(a[i][j] == 'o') st = {i, j}; if(a[i][j] == 'x') en = {i, j}; d[i][j] = 1e9; } } for(int i = 1; i <= r; ++i){ for(int j = 1; j <= s; ++j){ // up if(i - 1 > 0){ if(a[i][j] == '^') adj[i][j].push_back({{i - 1, j}, 0}); else adj[i][j].push_back({{i - 1, j}, 1}); } // down if(i + 1 <= r){ if(a[i][j] == 'v') adj[i][j].push_back({{i + 1, j}, 0}); else adj[i][j].push_back({{i + 1, j}, 1}); } // left if(j - 1 > 0){ if(a[i][j] == '<') adj[i][j].push_back({{i, j - 1}, 0}); else adj[i][j].push_back({{i, j - 1}, 1}); } if(j + 1 <= s){ if(a[i][j] == '>') adj[i][j].push_back({{i, j + 1}, 0}); else adj[i][j].push_back({{i, j + 1}, 1}); } } } // 0 - 1 BFS deque<pair<int, int>> q; q.push_back(st); d[st.first][st.second] = -1; trace[st.first][st.second] = st; while(!q.empty()){ int x = q.front().first, y = q.front().second; q.pop_front(); vis[x][y] = 1; for(auto k : adj[x][y]){ int i = k.first.first, j = k.first.second, w = k.second; if(vis[i][j]) continue; if(d[x][y] + w < d[i][j]){ trace[i][j] = {x, y}; d[i][j] = d[x][y] + w; if(w == 0) q.push_front({i, j}); else q.push_back({i, j}); } } } int ans = d[en.first][en.second]; debug(ans, trace[en.first][en.second]); int i = en.first, j = en.second; while(i != st.first or j != st.second){ int x = trace[i][j].first, y = trace[i][j].second; if(x == i + 1){ a[i + 1][j] = '^'; } else if(x == i - 1){ a[i - 1][j] = 'v'; } else if(y == j + 1){ a[i][j + 1] = '<'; } else if(y == j - 1){ a[i][j - 1] = '>'; } else{ assert(0); } debug(i, j, x, y); i = x,j = y; } a[i][j] = 'o'; cout << ans << '\n'; for(int i = 1; i <= r; ++i){ for(int j = 1; j <= s; ++j){ cout << a[i][j]; } cout << "\n"; } } int32_t main() { cin.tie(nullptr)->sync_with_stdio(0); int test = 1; // cin >> test; for(int i = 1; i <= test; ++i){ solve(); } cerr << "\nTime elapsed: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms.\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...