#include<bits/stdc++.h>
#ifdef LOCAL
#include "Essentials/algo/debug.h"
#else
#define debug(...) 69
#endif
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int N = 2e3 + 23;
const int inf = 1e9;
#define F first
#define S second
#define pb push_back
#define kill(x) cout<<x<<endl, exit(0);
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
#define lc (v << 1)
#define rc ((v<<1) |1)
int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};
// v > ^ <
int n,m;
char a[N][N];
pii par[N][N];
bool mark[N][N];
int dist[N][N];
deque<pii> Q;
int val[300];
priority_queue<pair<int,pii>, vector<pair<int,pii>> , greater<pair<int,pii>>> pq;
void bfs(int x,int y) {
par[x][y] = {0,0};
for(int i = 0 ; i< N ; i ++) fill(dist[i],dist[i] + N, inf);
pq.push({0,{x,y}});
dist[x][y] = 0;
while(sz(pq)) {
auto [x,y] = pq.top().S; pq.pop();
if(mark[x][y]) continue;
mark[x][y] = true;
//if(a[x][y] == 'x') return;
for(int i = 0 ; i < 4 ; i ++) {
int w = ((val[a[x][y]] == i) || (val[a[x][y]] == 5) ? 0 : 1);
int x2=x + dx[i],y2 = y + dy[i];
debug(x2,y2,w);
if(x2 < 0 || x2 > n || y2 <0 || y2 > m || mark[x2][y2]) continue;
if(dist[x][y] +w < dist[x2][y2]) {
dist[x2][y2] = dist[x][y] + w;
par[x2][y2] = {x,y};
pq.push( { dist[x2][y2], {x2,y2}});
}
}
}
}
int32_t main() {
cin.tie(nullptr)->sync_with_stdio(false);
val['v'] = 0;
val['>'] = 1;
val['^'] = 2;
val['<'] = 3;
val['.'] = 4;
val['x'] = val['o'] = 5;
cin>>n>>m;
pii start,end;
for(int i = 1; i <= n; i ++) for(int j= 1; j <= m ;j ++) {
cin>>a[i][j];
if(a[i][j] == 'o') {
start = {i,j};
} else if(a[i][j] == 'x') {
end = {i,j};
}
}
bfs(start.F,start.S);
cout<<dist[end.F][end.S] << '\n';
int x = end.F,y = end.S;
while(true) {
auto [x2,y2] = par[x][y];
if(a[x][y] == 'o' || a[x2][y2] == 'o') break;
debug(x,y,par[x][y]);
if(a[x2][y2] != 'o') {
if(x2 == x) {
if(y2+1 == y) {
a[x2][y2] = '>';
} else {
a[x2][y2] = '<';
}
} else {
if(x2+1 == x) {
a[x2][y2] = 'v';
} else {
a[x2][y2] = '^';
}
}
}
x = x2,y = y2;
}
for(int i =1; i <= n ; i++) {
for(int j = 1; j <= m ; j ++) {
cout<<a[i][j];
}
cout<<'\n';
}
return 0;
}
// Jumpsuit, Jumpsuit cover me!
// Jumpsuit, Jumpsuit cover me!
Compilation message
Main.cpp: In function 'void bfs(int, int)':
Main.cpp:49:24: warning: array subscript has type 'char' [-Wchar-subscripts]
49 | int w = ((val[a[x][y]] == i) || (val[a[x][y]] == 5) ? 0 : 1);
| ~~~~~~^
Main.cpp:49:47: warning: array subscript has type 'char' [-Wchar-subscripts]
49 | int w = ((val[a[x][y]] == i) || (val[a[x][y]] == 5) ? 0 : 1);
| ~~~~~~^
Main.cpp:5:20: warning: statement has no effect [-Wunused-value]
5 | #define debug(...) 69
| ^~
Main.cpp:51:4: note: in expansion of macro 'debug'
51 | debug(x2,y2,w);
| ^~~~~
Main.cpp: In function 'int32_t main()':
Main.cpp:5:20: warning: statement has no effect [-Wunused-value]
5 | #define debug(...) 69
| ^~
Main.cpp:86:3: note: in expansion of macro 'debug'
86 | debug(x,y,par[x][y]);
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
21080 KB |
Output is correct |
| 2 |
Correct |
5 ms |
21336 KB |
Output is correct |
| 3 |
Correct |
5 ms |
21084 KB |
Output is correct |
| 4 |
Correct |
4 ms |
21084 KB |
Output is correct |
| 5 |
Correct |
4 ms |
21084 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
21080 KB |
Output is correct |
| 2 |
Correct |
5 ms |
21336 KB |
Output is correct |
| 3 |
Correct |
5 ms |
21084 KB |
Output is correct |
| 4 |
Correct |
4 ms |
21084 KB |
Output is correct |
| 5 |
Correct |
4 ms |
21084 KB |
Output is correct |
| 6 |
Correct |
97 ms |
32884 KB |
Output is correct |
| 7 |
Correct |
130 ms |
40968 KB |
Output is correct |
| 8 |
Correct |
249 ms |
45876 KB |
Output is correct |
| 9 |
Correct |
521 ms |
56132 KB |
Output is correct |
| 10 |
Correct |
645 ms |
59740 KB |
Output is correct |
| 11 |
Correct |
898 ms |
72052 KB |
Output is correct |
