Submission #1269050

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269050		ducdev	Nautilus (BOI19_nautilus)	C++17	66 / 100	1101 ms	159832 KiB

nautilus

// Author: 4uckd3v - Nguyen Cao Duc
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAX_N = 500;
const int MAX_K = 5000;
const int MOD = 1e9 + 7;

struct Node {
    int x, y, d;

    Node() {};
    Node(int x, int y, int d) : x(x), y(y), d(d) {};
};

int m, n, k;
string dir;
bitset<MAX_K + 5> vis[MAX_N + 5][MAX_N + 5];
char a[MAX_N + 5][MAX_N + 5];

bool valid(int x, int y) {
    return (x >= 1 && x <= m && y >= 1 && y <= n && a[x][y] == '.');
};

void bfs() {
    queue<Node> q;
    for (int x = 1; x <= m; x++) {
        for (int y = 1; y <= n; y++) {
            if (a[x][y] == '.') q.push(Node(x, y, 0));
        };
    };

    while (!q.empty()) {
        int x = q.front().x;
        int y = q.front().y;
        int d = q.front().d;
        q.pop();

        if (d == k) continue;

        if (dir[d + 1] == 'W' || dir[d + 1] == '?') {
            if (valid(x, y - 1)) {
                if (!vis[x][y - 1].test(d + 1)) {
                    q.push(Node(x, y - 1, d + 1));
                    vis[x][y - 1].set(d + 1);
                };
            };
        };
        if (dir[d + 1] == 'N' || dir[d + 1] == '?') {
            if (valid(x - 1, y)) {
                if (!vis[x - 1][y].test(d + 1)) {
                    q.push(Node(x - 1, y, d + 1));
                    vis[x - 1][y].set(d + 1);
                };
            };
        };
        if (dir[d + 1] == 'S' || dir[d + 1] == '?') {
            if (valid(x + 1, y)) {
                if (!vis[x + 1][y].test(d + 1)) {
                    q.push(Node(x + 1, y, d + 1));
                    vis[x + 1][y].set(d + 1);
                };
            };
        };
        if (dir[d + 1] == 'E' || dir[d + 1] == '?') {
            if (valid(x, y + 1)) {
                if (!vis[x][y + 1].test(d + 1)) {
                    q.push(Node(x, y + 1, d + 1));
                    vis[x][y + 1].set(d + 1);
                };
            };
        };
    };
};

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if (fopen("MAIN.INP", "r")) {
        freopen("MAIN.INP", "r", stdin);
        freopen("MAIN.OUT", "w", stdout);
    };

    cin >> m >> n >> k;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> a[i][j];
        };
    };
    cin >> dir;
    dir = " " + dir;

    bfs();

    int res = 0;

    for (int x = 1; x <= m; x++) {
        for (int y = 1; y <= n; y++) {
            if (vis[x][y].test(k)) res++;
        };
    };

    cout << res << '\n';
};

Compilation message (stderr)

nautilus.cpp: In function 'int main()':
nautilus.cpp:82:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |         freopen("MAIN.INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
nautilus.cpp:83:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |         freopen("MAIN.OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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