#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization("unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define all(x) x.begin(), x.end()
typedef pair<int, int> II;
template<typename T> bool maximize(T& a, T b) {return (a < b ? a = b, 1 : 0);}
template<typename T> bool minimize(T& a, T b) {return (a > b ? a = b, 1 : 0);}
const int INF = (int) 1e18;
const int MOD = 1e9 + 7;
const int N = 2e3 + 1;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
int n, m;
int xs, ys, xe, ye, d[N][N];
char a[N][N];
bool checkDir(const int &num, const char &dir)
{
if(dir == '.') return 1;
if(num == 0 && dir == '^') return 0;
if(num == 1 && dir == '>') return 0;
if(num == 2 && dir == 'v') return 0;
if(num == 3 && dir == '<') return 0;
return 1;
}
II trace[N][N];
void BFS()
{
queue<II> Q;
Q.push({xs, ys});
d[xs][ys] = 0;
while(Q.size())
{
auto cur = Q.front();
Q.pop();
if(a[cur.x][cur.y] == 'x') continue;
for(int i = 0; i < 4; i++)
{
const int &X = cur.first + dx[i];
const int &Y = cur.second + dy[i];
if(X < 1 || X > n || Y < 1 || Y > m) continue;
if(minimize(d[X][Y], d[cur.first][cur.second] + checkDir(i, a[cur.first][cur.second])))
{
trace[X][Y] = {cur.first, cur.second};
Q.push({X, Y});
}
}
}
}
void Trace()
{
II cur = {xe, ye};
while(cur.first != xs || cur.second != ys)
{
II new_cur = trace[cur.first][cur.second];
const int &X = new_cur.first;
const int &Y = new_cur.second;
if(cur.first > X) a[X][Y] = 'v';
else if(cur.first < X) a[X][Y] = '^';
else if(cur.second < Y) a[X][Y] = '<';
else a[X][Y] = '>';
cur = new_cur;
}
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
memset(d, 0x3f, sizeof(d));
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) scanf("%s", a[i] + 1);
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
{
//cin >> a[i][j];
if(a[i][j] == 'o') xs = i, ys = j;
else if (a[i][j] == 'x') xe = i, ye = j;
}
BFS();
Trace();
printf("%d\n", d[xe][ye] - 1);
a[xs][ys] = 'o';
for(int i = 1; i <= n; i++) puts(a[i] + 1);
// {
// printf("%s", a[i] + 1);
// printf("\n");
// }
return 0;
}
Compilation message
Main.cpp:3: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
3 | #pragma GCC optimization("unroll-loops")
|
Main.cpp: In function 'void BFS()':
Main.cpp:47:12: error: 'struct std::pair<int, int>' has no member named 'x'
47 | if(a[cur.x][cur.y] == 'x') continue;
| ^
Main.cpp:47:19: error: 'struct std::pair<int, int>' has no member named 'y'
47 | if(a[cur.x][cur.y] == 'x') continue;
| ^
Main.cpp: In function 'int main()':
Main.cpp:92:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
92 | scanf("%d%d", &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:93:38: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
93 | for(int i = 1; i <= n; i++) scanf("%s", a[i] + 1);
| ~~~~~^~~~~~~~~~~~~~~~
