Submission #527938

#	Time	Username	Problem	Language	Result	Execution time	Memory
527938		jalsol	Nautilus (BOI19_nautilus)	C++11	66 / 100	502 ms	262148 KiB

nautilus

#include <bits/stdc++.h>

using namespace std;

#define Task ""

struct __Init__ {
    __Init__() {
        cin.tie(nullptr)->sync_with_stdio(false);
        if (fopen(Task".inp", "r")) {
            freopen(Task".inp", "r", stdin);
            freopen(Task".out", "w", stdout); }
    }
} __init__;

using ll = long long;

#ifdef LOCAL
//#define debug(x) cerr << "[" #x " = " << x << "]\n";
#include "debugger.h"
#else
#define debug(...)
#endif // LOCAL

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define fi first
#define se second

#define For(i, l, r) for (int i = (l); i <= (r); ++i)
#define Ford(i, r, l) for (int i = (r); i >= (l); --i)
#define Rep(i, n) For (i, 0, (n) - 1)
#define Repd(i, n) Ford (i, (n) - 1, 0)

template<class C> int isz(const C& c) { return c.size(); }
template<class T> bool chmin(T& a, const T& b) { if (a > b) { a = b; return true; } return false; }
template<class T> bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } return false; }

constexpr int eps = 1e-9;
constexpr int inf = 1e9;
constexpr ll linf = 1e18;

/// ============================================================================

constexpr int maxN = 500 + 5;
constexpr int maxS = 5000 + 5;
constexpr const char* dirC = "NESW";
constexpr int dx[4] = {-1, 0, 1, 0};
constexpr int dy[4] = {0, 1, 0, -1};

struct State {
    int t, x, y;
};

int n, m, ns;
char a[maxN][maxN];
char s[maxS];

queue<State> q;
vector<vector<vector<bool>>> vis;
int ans;

vector<int8_t> getDir(char c) {
    switch (c) {
        case '?': return {0, 1, 2, 3};
        case 'N': return {0};
        case 'E': return {1};
        case 'S': return {2};
        case 'W': return {3};
        default: assert(false);
    }
}

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

void Bfs() {
    while (isz(q)) {
        int t = q.front().t;
        int x = q.front().x;
        int y = q.front().y;
        q.pop();

        if (t == ns) continue;

        for (int8_t i : getDir(s[t + 1])) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (!inside(nx, ny) || a[nx][ny] == '#') {
                continue;
            }

            if (!vis[t + 1][nx][ny]) {
                vis[t + 1][nx][ny] = true;
                q.push({t + 1, nx, ny});
            }
        }
    }
}

signed main() {
    cin >> n >> m >> ns;
    For (i, 1, n) cin >> (a[i] + 1);
    cin >> (s + 1);

    vis.assign(ns + 1, vector<vector<bool>>(n + 1, vector<bool>(m + 1)));

    For (i, 1, n) {
        For (j, 1, m) {
            if (a[i][j] == '.') {
                q.push({0, i, j});
                vis[0][i][j] = true;
            }
        }
    }

    Bfs();

    For (i, 1, n) {
        For (j, 1, m) {
            ans += vis[ns][i][j];
        }
    }

    cout << ans << '\n';
}

/**
    dp[t][x][y] = 0/1
    5000 * 500 * 500 => too much
**/

Compilation message (stderr)

nautilus.cpp: In constructor '__Init__::__Init__()':
nautilus.cpp:11:20: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |             freopen(Task".inp", "r", stdin);
      |             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
nautilus.cpp:12:20: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |             freopen(Task".out", "w", stdout); }
      |             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 29 / 29
• Subtask 2: 37 / 37
• Subtask 3: 0 / 34