#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> ii;
typedef pair<ll, ii> iii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef vector<vii> vvii;
#define task "test"
#define fastIO ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define forw(i, l, r) for( ll i = (l) ; i < (r) ; i++ )
#define forb(i, r, l) for( ll i = (r) ; i >= (l) ; i-- )
#define numBit(x) (__builtin_popcountll(1ll * (x)))
#define getBit(x, i) ((x) >> (i) & 1)
#define sz(x) (int)x.size()
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define debug(x) cerr << #x << " = " << x << '\n';
const int N = 2e3 + 7;
const ll inf = 0x3f3f3f3f;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};
int n, m, d[N][N];
ii st, des, tr[N][N];
char ch[N][N];
int get(char ch) {
if (ch == '^') return 0;
if (ch == '<') return 1;
if (ch == 'v') return 2;
if (ch == '>') return 3;
return -1;
}
int getindx(ii x, ii y) {
forw(i, 0, 4) {
ii tmp = mp(x.fi + dx[i], x.se + dy[i]);
if (tmp == y) return i;
}
return 0;
}
bool valid(ii u) {
return u.fi >= 0 && u.fi < n && u.se >= 0 && u.se < m;
}
void dijktra() {
memset(d, 0x3f, sizeof d);
priority_queue<iii, vector<iii>, greater<iii>> pq;
pq.push(mp(0, st));
d[st.fi][st.se] = 0;
while (sz(pq)) {
ii u = pq.top().se;
int w = pq.top().fi;
pq.pop();
int idx = get(ch[u.fi][u.se]);
if (ch[u.fi][u.se] == 'o') idx = -1;
if (ch[u.fi][u.se] == 'x') return;
forw(i, 0, 4) {
ii v = mp(u.fi + dx[i], u.se + dy[i]);
// if (u.fi == 0 && u.se == 2) cerr << v.fi << ' ' << v.se << endl;
if (valid(v) && d[v.fi][v.se] > d[u.fi][u.se] + (i != idx)) {
d[v.fi][v.se] = d[u.fi][u.se] + (i != idx);
tr[v.fi][v.se] = mp(u.fi, u.se);
pq.push(mp(d[v.fi][v.se], mp(v.fi, v.se)));
}
}
}
}
void trace() {
// des = tr[des.fi][des.se];
for (; tr[des.fi][des.se].fi != -1; ) {
// cerr << des.fi << ' ' << des.se << endl;
int idx = getindx(mp(des.fi, des.se), tr[des.fi][des.se]);
des = tr[des.fi][des.se];
if (ch[des.fi][des.se] == 'o') return;
if (!idx) ch[des.fi][des.se] = 'v';
else if (idx == 1) ch[des.fi][des.se] = '>';
else if (idx == 2) ch[des.fi][des.se] = '^';
else ch[des.fi][des.se] = '<';
}
}
int main() {
fastIO;
memset(tr, -1, sizeof tr);
cin >> n >> m;
forw(i, 0, n) forw(j, 0, m) {
cin >> ch[i][j];
if (ch[i][j] == 'o') st = mp(i, j);
if (ch[i][j] == 'x') des = mp(i, j);
}
dijktra();
cout << d[des.fi][des.se] - 1 << endl;
trace();
forw(i, 0, n) {
forw(j, 0, m) cout << ch[i][j];
cout << '\n';
}
}
Compilation message
Main.cpp: In function 'void dijktra()':
Main.cpp:72:9: warning: unused variable 'w' [-Wunused-variable]
72 | int w = pq.top().fi;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
41 ms |
79076 KB |
Output is correct |
| 2 |
Correct |
39 ms |
79156 KB |
Output is correct |
| 3 |
Correct |
36 ms |
79096 KB |
Output is correct |
| 4 |
Correct |
42 ms |
79168 KB |
Output is correct |
| 5 |
Correct |
38 ms |
79124 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
41 ms |
79076 KB |
Output is correct |
| 2 |
Correct |
39 ms |
79156 KB |
Output is correct |
| 3 |
Correct |
36 ms |
79096 KB |
Output is correct |
| 4 |
Correct |
42 ms |
79168 KB |
Output is correct |
| 5 |
Correct |
38 ms |
79124 KB |
Output is correct |
| 6 |
Correct |
115 ms |
80932 KB |
Output is correct |
| 7 |
Correct |
136 ms |
84124 KB |
Output is correct |
| 8 |
Correct |
282 ms |
82692 KB |
Output is correct |
| 9 |
Correct |
548 ms |
94452 KB |
Output is correct |
| 10 |
Correct |
768 ms |
86076 KB |
Output is correct |
| 11 |
Correct |
1304 ms |
107756 KB |
Output is correct |
