/**Bogosort**/
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define fo(i, a, b) for (int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for (int i = (a); i >= (b); --i)
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define maxn 405
#define maxm 1000006
#define maxc 1000000007
#define pii pair <int,int>
#define ii pair <int,int>
#define Task ""
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
template <typename T> inline void read(T &x){char c;bool nega=0;while((!isdigit(c=getchar()))&&(c!='-'));if(c=='-'){nega=1;c=getchar();}x=c-48;while(isdigit(c=getchar())) x=x*10+c-48;if(nega) x=-x;}
template <typename T> inline void writep(T x){if(x>9) writep(x/10);putchar(x%10+48);}
template <typename T> inline void write(T x){if(x<0){putchar('-');x=-x;}writep(x);putchar(' ');}
template <typename T> inline void writeln(T x){write(x);putchar('\n');}
using namespace std;
int n, m, d[10005];
char c[10005];
ii start;
int End;
inline int cv(int x, int y) {
return (x - 1) * m + y;
}
ii cv2(int x) {
return make_pair((x - 1) / m + 1, (x - 1) % m + 1);
}
inline bool valid(int x, int y) {
return (x && y && x <= n && y <= m && c[cv(x, y)] != '.');
}
void dfs(int u) {
if(u == cv(start.F, start.S)) return;
int x = cv2(u).F;
int y = cv2(u).S;
if(c[u] == '>') {
++y;
}
if(c[u] == '<') {
--y;
}
if(c[u] == 'v') {
++x;
}
if(c[u] == '^') {
--x;
}
if(!valid(x, y)) return;
if(d[cv(x, y)] > d[u]) {
d[cv(x, y)] = d[u];
dfs(cv(x, y));
}
}
int main() {
//srand(time(NULL));
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie();
// if(fopen(".inp", "r")) freopen(".inp", "r", stdin);
cin >> n >> m;
fo(i, 1, n) fo(j, 1, m) {
cin >> c[cv(i, j)];
if(c[cv(i, j)] == 'o') {
start = {i, j};
}
if(c[cv(i, j)] == 'x') {
End = cv(i, j);
}
}
int ans = 2e9;
int dir = 0;
int xs, ys;
xs = start.F;
ys = start.S + 1;
fo(i, 1, n) fo(j, 1, m) d[cv(i, j)] = 2e9;
if(xs && ys && xs <= n && ys <= m && c[cv(xs, ys)] != '.') {
d[cv(xs, ys)] = 1;
dfs(cv(xs, ys));
}
if(d[End] < ans && d[End]) {
ans = End;
dir = 0;
}
xs = start.F + 1;
ys = start.S;
fo(i, 1, n) fo(j, 1, m) d[cv(i, j)] = 2e9;
if(xs && ys && xs <= n && ys <= m && c[cv(xs, ys)] != '.') {
d[cv(xs, ys)] = 1;
dfs(cv(xs, ys));
}
if(d[End] < ans && d[End]) {
ans = End;
dir = 1;
}
xs = start.F - 1;
ys = start.S;
fo(i, 1, n) fo(j, 1, m) d[cv(i, j)] = 2e9;
if(xs && ys && xs <= n && ys <= m && c[cv(xs, ys)] != '.') {
d[cv(xs, ys)] = 1;
dfs(cv(xs, ys));
}
if(d[End] < ans && d[End]) {
ans = End;
dir = 2;
}
xs = start.F;
ys = start.S - 1;
fo(i, 1, n) fo(j, 1, m) d[cv(i, j)] = 2e9;
if(xs && ys && xs <= n && ys <= m && c[cv(xs, ys)] != '.') {
d[cv(xs, ys)] = 1;
dfs(cv(xs, ys));
}
if(d[End] < ans && d[End]) {
ans = End;
dir = 3;
}
if(ans == 2e9) {
cout << ":(";
return 0;
}
cout << ":)\n";
string s = "ENSW"; cout << s[dir];
return 0;
}
Compilation message
patkice.cpp:17: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
17 | #pragma GCC optimization ("O3")
|
patkice.cpp:18: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
18 | #pragma GCC optimization ("unroll-loops")
|
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
