Submission #1171224

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171224		achi	Patkice (COCI20_patkice)	C++17	30 / 50	0 ms	396 KiB

patkice

#include <bits/stdc++.h>

using namespace std;

vector<string> grid;
vector<vector<int>> dist;
vector<int> r = {0, -1, 1, 0}, c = {1, 0, 0, -1};
vector<char> possible = {'<', 'v', '^', '>'};
// E N S W
vector<char> moves = {'E', 'N', 'S', 'W'};
int R, S;

vector<pair<int,int>> getPos(int i, int j) {
    vector<pair<int, int>> ans;
    for (int d = 0; d < 4; d++) {
        int ui = i+r[d], uj = j+c[d];
        if (ui < 0 || uj < 0 || ui >= R || uj >= S || (grid[ui][uj] != possible[d] && grid[ui][uj] != 'o')) continue;
        ans.push_back({ui, uj});
    }
    return ans;
}

int main () {
    int ui = -1, uj = -1, vi, vj;
    cin >> R >> S;
    grid.resize(R);
    dist.assign(R, vector<int>(S, INT_MAX));
    for (int i = 0; i < R; i++) cin >> grid[i];
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < S; j++) {
            if (grid[i][j] == 'x') {
                ui = i;
                uj = j;
                break;
            }
        }
        if (ui != -1 && uj != -1) break;
    }

    queue<pair<int, int>> q;
    bool found = false;
    q.push({ui, uj});
    dist[ui][uj] = 0;
    while (!q.empty()) {
        tie(ui, uj) = q.front();
        q.pop();
        for (auto &[i, j] : getPos(ui, uj)) {
            if (dist[i][j] != INT_MAX) continue;
            if (grid[i][j] == 'o') {
                vi = i;
                vj = j;
                found = true;
                break;
            }
            dist[i][j] = dist[ui][uj] + 1;
            q.push({i, j});
        }
        if (found) break;
    }

    if (found) {
        cout << ":)\n";
        for (int i = 0; i < 4; i++) {
            int vii = vi+r[i], vjj = vj+c[i];
            if (vii < 0 || vjj < 0 || vii >= R || vjj >= S || dist[vii][vjj] == INT_MAX) continue;
            cout << moves[i];
        }
    }
    else {
        cout << ":(";
    }

    return 0;
}

• Subtask 1: 30 / 30
• Subtask 2: 0 / 20