/**
* author: wxhtzdy
* created: 02.07.2022 16:23:36
**/
#include <bits/stdc++.h>
using namespace std;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
vector<string> s(n);
for (int i = 0; i < n; i++) {
cin >> s[i];
}
int sx, sy, fx, fy;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (s[i][j] == 'o') {
sx = i;
sy = j;
}
if (s[i][j] == 'x') {
fx = i;
fy = j;
}
}
}
const int inf = (int) 1e7;
vector<vector<int>> dist(n, vector<int>(m, inf));
vector<int> prv(n * m, -1);
set<pair<int, int>> st;
dist[sx][sy] = 0;
st.emplace(0, sx * m + sy);
while (!st.empty()) {
auto it = st.begin();
int id = it->second;
int i = id / m;
int j = id % m;
st.erase(it);
vector<int> cost(4, 1);
if (s[i][j] == 'v') {
cost[0] = 0;
}
if (s[i][j] == '>') {
cost[1] = 0;
}
if (s[i][j] == '^') {
cost[2] = 0;
}
if (s[i][j] == '<') {
cost[3] = 0;
}
if (s[i][j] == 'o') {
cost = vector<int>(4, 0);
}
for (int d = 0; d < 4; d++) {
int ni = i + dx[d];
int nj = j + dy[d];
if (ni >= 0 && ni < n && nj >= 0 && nj < m && dist[ni][nj] > dist[i][j] + cost[d]) {
if (dist[ni][nj] != inf) {
st.erase(st.find(make_pair(dist[ni][nj], ni * m + nj)));
}
dist[ni][nj] = dist[i][j] + cost[d];
prv[ni * m + nj] = i * m + j;
st.emplace(make_pair(dist[ni][nj], ni * m + nj));
}
}
}
cout << dist[fx][fy] << '\n';
int x = fx * m + fy;
vector<int> path;
while (x != -1) {
path.push_back(x);
x = prv[x];
}
for (int i = 1; i < (int) path.size() - 1; i++) {
int xa = path[i] / m;
int ya = path[i] % m;
int xb = path[i - 1] / m;
int yb = path[i - 1] % m;
if (xa + 1 == xb) {
s[xa][ya] = 'v';
}
if (xa - 1 == xb) {
s[xa][ya] = '^';
}
if (ya + 1 == yb) {
s[xa][ya] = '>';
}
if (ya - 1 == yb) {
s[xa][ya] = '<';
}
}
for (int i = 0; i < n; i++) {
cout << s[i] << '\n';
}
return 0;
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:75:22: warning: 'fy' may be used uninitialized in this function [-Wmaybe-uninitialized]
75 | cout << dist[fx][fy] << '\n';
| ^
Main.cpp:75:18: warning: 'fx' may be used uninitialized in this function [-Wmaybe-uninitialized]
75 | cout << dist[fx][fy] << '\n';
| ^
Main.cpp:39:24: warning: 'sy' may be used uninitialized in this function [-Wmaybe-uninitialized]
39 | st.emplace(0, sx * m + sy);
| ~~~~~~~^~~~
Main.cpp:39:20: warning: 'sx' may be used uninitialized in this function [-Wmaybe-uninitialized]
39 | st.emplace(0, sx * m + sy);
| ~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
324 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
320 KB |
Output is correct |
| 4 |
Correct |
1 ms |
316 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
324 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
320 KB |
Output is correct |
| 4 |
Correct |
1 ms |
316 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
95 ms |
5352 KB |
Output is correct |
| 7 |
Correct |
116 ms |
9540 KB |
Output is correct |
| 8 |
Correct |
265 ms |
13312 KB |
Output is correct |
| 9 |
Correct |
509 ms |
32972 KB |
Output is correct |
| 10 |
Correct |
623 ms |
31772 KB |
Output is correct |
| 11 |
Correct |
988 ms |
60248 KB |
Output is correct |
