#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("00")
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int, int> pii;
ll time() {return chrono::system_clock().now().time_since_epoch().count();}
mt19937 rnd(time());
const int inf = 1e9;
const ll inf64 = 1e18;
#define ft first
#define fin(x) ifstream cin("x.in");
#define fout(x) ofstream cout("x.out");
#define sd second
#define pb push_back
#define sz(x) (int)x.size()
char grid[2001][2001];
int dst[2001][2001];
bool was[2001][2001];
array<int, 2> mem[2001][2001];
int steps[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
void solve()
{
int n, m;
cin >> n >> m;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
dst[i][j] = inf;
int sx = 0, sy = 0, ex = 0, ey = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
{
cin >> grid[i][j];
if (grid[i][j] == 'o')
{
sx = i;
sy = j;
}
else if (grid[i][j] == 'x')
{
ex = i;
ey = j;
}
}
queue< pair< pair<int, int>, int > > q;
q.push({{0, sx}, sy});
was[sx][sy] = true;
dst[sx][sy] = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
mem[i][j] = {-1, -1};
while (!q.empty())
{
int cost = -q.front().ft.ft;
int fx = q.front().ft.sd;
int fy = q.front().sd;
q.pop();
if (cost > dst[fx][fy])
continue;
was[fx][fy] = true;
for (int i = 0; i < 4; i++)
{
int cx = fx + steps[i][0];
int cy = fy + steps[i][1];
int pay = 1;
if (fx == sx && fy == sy)
pay = 0;
if (steps[i][0] == 1 && grid[fx][fy] == 'v')
pay = 0;
if (steps[i][0] == -1 && grid[fx][fy] == '^')
pay = 0;
if (steps[i][1] == 1 && grid[fx][fy] == '>')
pay = 0;
if (steps[i][1] == -1 && grid[fx][fy] == '<')
pay = 0;
if (!(cx >= 0 && cx < n && cy >= 0 && cy < m && !was[cx][cy]))
continue;
if (cost + pay < dst[cx][cy])
{
dst[cx][cy] = cost + pay;
q.push({{-(cost + pay), cx}, cy});
mem[cx][cy] = {fx, fy};
}
}
}
vector< array<int, 2> > path;
int x = ex, y = ey;
while (x != sx || y != sy)
{
path.pb({x, y});
auto nx = mem[x][y];
x = nx[0];
y = nx[1];
}
path.pb({sx, sy});
reverse(path.begin(), path.end());
for (int i = 0; i < sz(path); i++)
{
if (path[i + 1][0] - path[i][0] == 1)
{
grid[path[i][0]][path[i][1]] = 'v';
}
else if (path[i][0] - path[i + 1][0] == 1)
{
grid[path[i][0]][path[i][1]] = '^';
}
else if (path[i + 1][1] - path[i][1] == 1)
{
grid[path[i][0]][path[i][1]] = '>';
}
else if (path[i][1] - path[i + 1][1] == 1)
{
grid[path[i][0]][path[i][1]] = '<';
}
}
grid[sx][sy] = 'o';
grid[ex][ey] = 'x';
cout << dst[ex][ey] << '\n';
for (int i = 0; i < n; i++, cout << '\n')
for (int j = 0; j < m; j++)
cout << grid[i][j];
}
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifdef _LOCAL_
system("color 2");
#endif // _LOCAL_
int t = 1;
while (t--)
solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
492 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
492 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
492 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
492 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
