# include <bits/stdc++.h>
# define pb push_back
# define ff first
# define ss second
# define nl "\n"
# define sz(x) ((int)(x).size())
# define deb(x) cerr << #x << " = " << x << endl;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const ll maxn = 1e5 + 25;
const ll inf = 1e18 + 0;
const ll mod = 1e9 + 7;
const ll dx[] = {0, -1, 1, 0};
const ll dy[] = {1, 0, 0, -1};
const ld eps = 1e-6;
using namespace std;
ll n, m;
char c[103][103];
ll d[103][103][4];
pair <ll, ll> dir (char c)
{
if (c == '>') return {0, 1};
if (c == '^') return {-1, 0};
if (c == 'v') return {1, 0};
if (c == '<') return {0, -1};
return {0, 0};
}
void dijkstra (ll xx, ll yy, ll k)
{
for (ll i = 1; i <= n; ++i)
{
for (ll j = 1; j <= n; ++j)
{
d[i][j][k] = inf;
}
}
if (c[xx][yy] == '.') return;
d[xx][yy][k] = 1;
set < pair <ll, pair <ll, ll> > > q;
q.insert({d[xx][yy][k], {xx, yy}});
while (!q.empty())
{
ll x = (q.begin() -> ss.ff);
ll y = (q.begin() -> ss.ss);
q.erase(q.begin());
pair <ll, ll> qw = dir(c[x][y]);
ll to_x = x + qw.ff;
ll to_y = y + qw.ss;
if (d[to_x][to_y][k] > d[x][y][k] + 1 && (c[to_x][to_y] != '.' && c[to_x][to_y] != 'o'))
{
q.erase({d[to_x][to_y][k], {to_x, to_y}});
d[to_x][to_y][k] = d[x][y][k] + 1;
q.insert({d[to_x][to_y][k], {to_x, to_y}});
}
}
}
void ma1n ()
{
cin >> n >> m;
ll st_x = -1, st_y = -1;
ll fn_x = -1, fn_y = -1;
for (ll i = 1; i <= n; ++i)
{
for (ll j = 1; j <= n; ++j)
{
cin >> c[i][j];
if (c[i][j] == 'o')
{
st_x = i;
st_y = j;
}
if (c[i][j] == 'x')
{
fn_x = i;
fn_y = j;
}
}
}
ll mn = inf;
for (ll k = 0; k < 4; ++k)
{
d[st_x][st_y][k] = 0;
ll x = st_x + dx[k];
ll y = st_y + dy[k];
dijkstra(x, y, k);
mn = min(mn, d[fn_x][fn_y][k]);
//cout << d[fn_x][fn_y][k] << nl;
}
for (ll k = 0; k < 4 && mn != inf; ++k)
{
if (d[fn_x][fn_y][k] == mn)
{
cout << ":)" << nl;
if (k == 0) cout << "E";
if (k == 1) cout << "N";
if (k == 2) cout << "S";
if (k == 3) cout << "W";
return;
}
}
cout << ":(";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
// freopen("file.in", "r", stdin);
// freopen("file.out", "w", stdout);
int ttt = 1;
// cin >> ttt;
for (int test = 1; test <= ttt; ++test)
{
// cout << "Case " << test << ":" << ' ';
ma1n();
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
