Submission #1183913

#TimeUsernameProblemLanguageResultExecution timeMemory
1183913nagorn_phPatkice (COCI20_patkice)C++20
50 / 50
0 ms400 KiB
#include <bits/stdc++.h>
#define int long long
#define double long double
#define pii pair <int,int>
#define tiii tuple <int, int, int>
#define f first
#define s second
#define all(x) x.begin(), x.end()
#define ub(a, b) upper_bound(a.begin(), a.end(), b) - a.begin()
#define lb(a, b) lower_bound(a.begin(), a.end(), b) - a.begin()
#define ve vector
#define graph(a, n) vector <int> a[n];
#define wgraph(a, n) vector <pii> a[n];
#define emb emplace_back
#define em emplace
#define ins insert
#define er erase
#define iShowSpeed cin.tie(NULL)->sync_with_stdio(false)

using namespace std;

template <typename T>
using greater_priority_queue = priority_queue<T, vector<T>, greater<T>>;

const int mod = 1e9 + 7;
const int inf = 1e18;
const int N = 1e2 + 5;
const int M = 1e2 + 5;

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

int n, m, sx, sy, a[N][M];
bool visited[N][M];

bool inside(int x, int y) {
    return x > 0 && x <= n && y > 0 && y <= m;
}

int32_t main(){
    iShowSpeed;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            char c; cin >> c;
            if (c == '<') a[i][j] = 3;
            else if (c == '>') a[i][j] = 1;
            else if (c == '^') a[i][j] = 2;
            else if (c == '.') a[i][j] = -1;
            else if (c == 'x') a[i][j] = inf;
            else a[i][j] = 0;
            if (c == 'o') sx = i, sy = j;
        }
    }
    queue <tuple <int, int, char>> q;
    vector <tuple <char, int, int>> t;
    for (int i = 0; i < 4; i++) {
        int x = sx, y = sy;
        int nx = x + dx[i], ny = y + dy[i];
        if (inside(nx, ny)) {
            char ch;
            if (i == 0) ch = 'S';
            if (i == 1) ch = 'E';
            if (i == 2) ch = 'N';
            if (i == 3) ch = 'W';
            t.emb(ch, nx, ny);
            visited[nx][ny] = true;
        }
    }
    // cout << sx << " " << sy << "\n";
    sort(all(t));
    // cout << a[2][3] << ": ";
    // cout << 2 + dx[a[2][3]] << " " << 3 + dy[a[2][3]] << "\n";
    for (auto [ch, x, y] : t) q.emplace(x, y, ch);
    while (!q.empty()) {
        auto [x, y, c] = q.front(); q.pop();
        if (a[x][y] == inf) return cout << ":)" << "\n" << c, 0;
        else if (a[x][y] == -1) continue;
        // cout << x << " " << y << ": " << c << "\n";
        int nx = x + dx[a[x][y]], ny = y + dy[a[x][y]];
        if (inside(nx, ny) && !visited[nx][ny]) {
            q.emplace(nx, ny, c);
            visited[nx][ny] = true;
        }
    }
    cout << ":(";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...