#include <bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 1e9 + 7;
const ll LOGN = 18;
const ll MAXN = 1e5 + 100;
vector<pair<int,pair<int,int>>> graph[2005][2005], rev[2005][2005];
int dist[2005][2005], vis[2005][2005];
vector<string> grid;
pair<int,int> s, e;
void change(int row, int col, int nrow, int ncol) {
if (nrow > row)
grid[row][col] = 'v';
else if (nrow < row)
grid[row][col] = '^';
else if (ncol < col)
grid[row][col] = '<';
else
grid[row][col] = '>';
}
void dfs(int row, int col, int target) {
vis[row][col] = true;
for (auto u : rev[row][col]) {
int w = u.f;
int nrow = u.s.f;
int ncol = u.s.s;
if (vis[nrow][ncol])
continue;
if (dist[nrow][ncol] + w == target) {
change(nrow, ncol, row, col);
dfs(nrow, ncol, target - w);
return ;
}
}
}
int main() {
fast
int r, c;
cin >> r >> c;
for (int i = 0; i < 2005; i++) {
for (int j = 0; j < 2005; j++)
dist[i][j] = 1e8;
}
grid = vector<string>(r);
for (int i = 0; i < r; i++)
cin >> grid[i];
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
if (grid[i][j] == '>') {
graph[i][j].push_back({0, {i, j+1}});
graph[i][j].push_back({1, {i+1, j}});
graph[i][j].push_back({1, {i, j-1}});
graph[i][j].push_back({1, {i-1, j}});
rev[i][j+1].push_back({0, {i, j}});
rev[i+1][j].push_back({1, {i, j}});
rev[i][j-1].push_back({1, {i, j}});
rev[i-1][j].push_back({1, {i, j}});
} else if (grid[i][j] == '<') {
graph[i][j].push_back({1, {i, j+1}});
graph[i][j].push_back({1, {i+1, j}});
graph[i][j].push_back({0, {i, j-1}});
graph[i][j].push_back({1, {i-1, j}});
rev[i][j+1].push_back({1, {i, j}});
rev[i+1][j].push_back({1, {i, j}});
rev[i][j-1].push_back({0, {i, j}});
rev[i-1][j].push_back({1, {i, j}});
} else if (grid[i][j] == 'v') {
graph[i][j].push_back({1, {i, j+1}});
graph[i][j].push_back({0, {i+1, j}});
graph[i][j].push_back({1, {i, j-1}});
graph[i][j].push_back({1, {i-1, j}});
rev[i][j+1].push_back({1, {i, j}});
rev[i+1][j].push_back({0, {i, j}});
rev[i][j-1].push_back({1, {i, j}});
rev[i-1][j].push_back({1, {i, j}});
} else if (grid[i][j] == '^') {
graph[i][j].push_back({1, {i, j+1}});
graph[i][j].push_back({1, {i+1, j}});
graph[i][j].push_back({1, {i, j-1}});
graph[i][j].push_back({0, {i-1, j}});
rev[i][j+1].push_back({1, {i, j}});
rev[i+1][j].push_back({1, {i, j}});
rev[i][j-1].push_back({1, {i, j}});
rev[i-1][j].push_back({0, {i, j}});
} else if (grid[i][j] == '.') {
graph[i][j].push_back({1, {i, j+1}});
graph[i][j].push_back({1, {i+1, j}});
graph[i][j].push_back({1, {i, j-1}});
graph[i][j].push_back({1, {i-1, j}});
rev[i][j+1].push_back({1, {i, j}});
rev[i+1][j].push_back({1, {i, j}});
rev[i][j-1].push_back({1, {i, j}});
rev[i-1][j].push_back({1, {i, j}});
} else if (grid[i][j] == 'o') {
s = {i, j};
graph[i][j].push_back({0, {i, j+1}});
graph[i][j].push_back({0, {i+1, j}});
graph[i][j].push_back({0, {i, j-1}});
graph[i][j].push_back({0, {i-1, j}});
rev[i][j+1].push_back({0, {i, j}});
rev[i+1][j].push_back({0, {i, j}});
rev[i][j-1].push_back({0, {i, j}});
rev[i-1][j].push_back({0, {i, j}});
} else
e = {i, j};
}
}
deque<pair<int,int>> dq;
dq.push_back(s);
dist[s.f][s.s] = 0;
while (!dq.empty()) {
int row = dq.front().f;
int col = dq.front().s;
dq.pop_front();
for (auto u : graph[row][col]) {
int w = u.f;
int nrow = u.s.f;
int ncol = u.s.s;
if (dist[nrow][ncol] > w + dist[row][col]) {
dist[nrow][ncol] = w + dist[row][col];
if (w == 1)
dq.push_back({nrow, ncol});
else
dq.push_front({nrow, ncol});
}
}
}
cout << dist[e.f][e.s] << "\n";
memset(vis, 0, sizeof(vis));
dfs(e.f, e.s, dist[e.f][e.s]);
grid[s.f][s.s] = 'o';
for (int i = 0; i < r; i++)
cout << grid[i] << "\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
201 ms |
417584 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
201 ms |
417584 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
