This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define pii pair<int, int>
struct st{
int i, j, k;
};
const int sz = 2005;
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
const char dc[] = {'>', 'v', '<', '^'};
char a[sz][sz];
int d[sz][sz];
st pre[sz][sz];
int n, m, S, T, U, V;
bool valid(int x, int y){
return (x >= 1 && x <= n && y >= 1 && y <= m);
}
void bfs(int x, int y){
deque<pair<int, pii>> q;
memset(d, 63, sizeof d);
q.push_front({0, {x, y}});
d[x][y] = 0;
pre[x][y] = {-1, -1, -1};
while(q.size()){
int x, y, w;
w = q.front().first;
tie(x, y) = q.front().second;
q.pop_front();
for(int i=0; i<4; ++i){
int u = x + dx[i];
int v = y + dy[i];
int c = (a[x][y] == 'o' ? 0 : (dc[i] != a[x][y]));
if(!valid(u, v) && a[u][v] == 'o'){
continue;
}
if(w + c < d[u][v]){
d[u][v] = w + c;
pre[u][v] = {x, y, i};
if(c == 0){
q.push_front({w+c, {u, v}});
}
else{
q.push_back({w+c, {u, v}});
}
}
}
// cout<<"-------------"<<endl;
}
}
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
//freopen("main.inp","r",stdin);
//freopen("main.out","w",stdout);
cin>>n>>m;
for(int i=1; i<=n; ++i){
for(int j=1; j<=m; ++j){
cin>>a[i][j];
if(a[i][j] == 'o'){
S = i;
T = j;
}
if(a[i][j] == 'x'){
U = i;
V = j;
}
pre[i][j] = {-1, -1, -1};
}
}
bfs(S, T);
cout<<d[U][V]<<endl;
int x, y, p;
x = U;
y = V;
p = pre[U][V].k;
while(min({x, y, p}) != -1){
if(a[x][y] != 'x' && a[x][y] != 'o'){
a[x][y] = dc[p];
}
st nxt = pre[x][y];
x = nxt.i;
y = nxt.j;
p = nxt.k;
}
for(int i=1; i<=n; ++i){
for(int j=1; j<=m; ++j){
cout<<a[i][j];
}
cout<<endl;
}
//1 0 1 1
//1 0 1 1
//0 1 1 1
//2 2 2 2
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |