#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 or vis[i][j]) return;
vis[i][j] = 1;
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};
}
}
}
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.fi != st.fi or ed.se != st.se){
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 time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
332 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
332 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
332 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
332 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
