This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define F first
#define S second
#define ALL(x) x.begin(), x.end()
#define MEM(x) memset(x, 0, sizeof(x))
#define MEMS(x) memset(x, -1, sizeof(x))
#define eb emplace_back
#define ep emplace
#define mkp make_pair
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
/*------------------------------------------------------------------*/
using pic = pair<int, char>;
const int N = 100 + 5;
char G[N][N];
bool vis[N][N];
pic ans[N][N];
int r, s, er, es, sr, ss;
bool check(int i, int j) {
return !vis[i][j] && i >= 0 && i < r && j >= 0 && j < s;
}
// E > N > S > W
pic bfs(int i, int j) {
queue<pii> que;
for(int i = 0; i < N; ++i)
for(int j = 0; j < N; ++j)
ans[i][j] = {INF, 'X'};
que.push({i, j}); ans[i][j] = {0, 'X'};
while(!que.empty()) {
auto u = que.front(); que.pop();
// cout << u.F << ' ' << u.S << '\n';
if(G[u.F][u.S] == 'o') {
if(u.S + 1 < s)
ans[u.F][u.S + 1] = {1, 'E'}, que.ep(u.F, u.S + 1);
if(u.S - 1 >= 0)
ans[u.F][u.S - 1] = {1, 'W'}, que.ep(u.F, u.S - 1);
if(u.F + 1 < r)
ans[u.F + 1][u.S] = {1, 'S'}, que.ep(u.F + 1, u.S);
if(u.F - 1 >= 0)
ans[u.F - 1][u.S] = {1, 'N'}, que.ep(u.F - 1, u.S);
}
if(G[u.F][u.S] == '>') {
if(mkp(ans[u.F][u.S].F + 1, ans[u.F][u.S].S) < ans[u.F][u.S + 1]) {
ans[u.F][u.S + 1] = {ans[u.F][u.S].F + 1, ans[u.F][u.S].S};
que.ep(u.F, u.S + 1);
}
}
if(G[u.F][u.S] == '<') {
if(mkp(ans[u.F][u.S].F + 1, ans[u.F][u.S].S) < ans[u.F][u.S - 1]) {
ans[u.F][u.S - 1] = {ans[u.F][u.S].F + 1, ans[u.F][u.S].S};
que.ep(u.F, u.S - 1);
}
}
if(G[u.F][u.S] == '^') {
if(mkp(ans[u.F][u.S].F + 1, ans[u.F][u.S].S) < ans[u.F - 1][u.S]) {
ans[u.F - 1][u.S] = {ans[u.F][u.S].F + 1, ans[u.F][u.S].S};
que.ep(u.F - 1, u.S);
}
}
if(G[u.F][u.S] == 'v') {
if(mkp(ans[u.F][u.S].F + 1, ans[u.F][u.S].S) < ans[u.F + 1][u.S]) {
ans[u.F + 1][u.S] = {ans[u.F][u.S].F + 1, ans[u.F][u.S].S};
que.ep(u.F + 1, u.S);
}
}
}
return ans[er][es];
}
inline void solve() {
cin >> r >> s;
for(int i = 0; i < r; ++i)
for(int j = 0; j < s; ++j) {
cin >> G[i][j];
if(G[i][j] == 'o')
sr = i, ss = j;
if(G[i][j] == 'x')
er = i, es = j;
}
auto ret = bfs(sr, ss);
if(ret.F == INF)
cout << ":(";
else
cout << ":)\n" << ret.S << '\n';
}
int main() {
cin.tie(0), ios::sync_with_stdio(0);
solve();
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |