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>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define N 100500
#define PB push_back
#define endl '\n'
#define pri(x) cout << x << endl
#define _ << " " <<
#define sz(x) int(x.size())
#define F first
#define S second
#define all(x) x.begin(), x.end()
using namespace std;
//using namespace __gnu_pbds;
typedef long long ll;
//typedef tree <int, null_type, less_equal <int>, rb_tree_tag, tree_order_statistics_node_update> ord_set;
int f[2005][2005];
pair <int, int> from[2005][2005];
int main()
{
ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// freopen("1.in", "r", stdin);
for (int i = 0; i < 2005; i++)
for (int j = 0; j < 2005; j++)
f[i][j] = 1e9;
int n, m;
cin >> n >> m;
string s[n];
for (int i = 0; i < n; i++)
cin >> s[i];
set <pair <int, pair <int, int> > > se; se.clear();
int xs, ys, xf, yf;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
{
if (s[i][j] == 'o')
{
xs = i; ys = j;
}
if (s[i][j] == 'x')
{
xf = i; yf = j;
}
}
f[xs][ys] = 0;
se.insert({0, {xs, ys}});
while (sz(se))
{
pair <int, int> pt = (*se.begin()).S;
se.erase(se.begin());
int i = pt.F, j = pt.S;
if (s[i][j] == 'x')
break;
int cx = pt.F, cy = pt.S;
if (s[i][j] == '>')
cy++;
else if (s[i][j] == '<')
cy--;
else if (s[i][j] == '^')
cx--;
else if (s[i][j] == 'v')
cx++;
if (0 <= cx && cx < n && cy >= 0 && cy < m && f[cx][cy] > f[i][j])
{
f[cx][cy] = f[i][j];
from[cx][cy] = {i, j};
se.insert({f[cx][cy], {cx, cy}});
}
int b[4][2] = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
for (int i = 0; i < 4; i++)
{
int cx = pt.F + b[i][0];
int cy = pt.S + b[i][1];
if (0 <= cx && cx < n && cy >= 0 && cy < m && f[cx][cy] > f[pt.F][pt.S] + 1)
{
f[cx][cy] = f[pt.F][pt.S] + 1;
from[cx][cy] = {pt.F, pt.S};
se.insert({f[cx][cy], {cx, cy}});
}
}
}
pri(f[xf][yf] - 1);
while (xf != xs || yf != ys)
{
pair <int, int> pt = from[xf][yf];
char c;
if (pt.S < yf)
c = '>';
else if (pt.S > yf)
c = '<';
else if (pt.F > xf)
c = '^';
else c = 'v';
xf = pt.F;
yf = pt.S;
s[xf][yf] = c;
}
s[xs][ys] = 'o';
for (int i = 0; i < n; i++)
cout << s[i] << endl;
}
Compilation message (stderr)
Main.cpp: In function 'int main()':
Main.cpp:139:13: warning: 'ys' may be used uninitialized in this function [-Wmaybe-uninitialized]
139 | s[xs][ys] = 'o';
| ^
Main.cpp:47:9: warning: 'xs' may be used uninitialized in this function [-Wmaybe-uninitialized]
47 | int xs, ys, xf, yf;
| ^~
Main.cpp:117:17: warning: 'yf' may be used uninitialized in this function [-Wmaybe-uninitialized]
117 | pri(f[xf][yf] - 1);
| ^
Main.cpp:117:17: warning: 'xf' may be used uninitialized in this function [-Wmaybe-uninitialized]
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |