제출 #1156990

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1156990		_callmelucian	Nautilus (BOI19_nautilus)	C++17	100 / 100	240 ms	964 KiB

nautilus

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;
using pl = pair<ll,ll>;
using pii = pair<int,int>;
using tpl = tuple<int,int,int>;
using ocean = bitset<500 * 500>;

#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())

ocean fltLeft, fltRight, fltUp, fltDown, dp, emptyCell;
int n, m, k;

int node (int i, int j) { return i * m + j; }

ocean moveLeft (const ocean &cur) {
    ocean ans = (cur & fltLeft) >> 1;
    return ans & emptyCell;
}

ocean moveRight (const ocean &cur) {
    ocean ans = (cur & fltRight) << 1;
    return ans & emptyCell;
}

ocean moveUp (const ocean &cur) {
    ocean ans = (cur & fltUp) >> m;
    return ans & emptyCell;
}

ocean moveDown (const ocean &cur) {
    ocean ans = (cur & fltDown) << m;
    return ans & emptyCell;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m >> k;

    /// read input & prep bitsets
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            char c; cin >> c;
            int curNode = node(i, j);
            if (c == '.') emptyCell[curNode] = 1;
            if (i > 0) fltUp[curNode] = 1;
            if (i + 1 < n) fltDown[curNode] = 1;
            if (j > 0) fltLeft[curNode] = 1;
            if (j + 1 < m) fltRight[curNode] = 1;
        }
    }

    string s; cin >> s;

    /// run modified BFS on bitset
    dp = emptyCell; // initially, all empty cells are available
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '?')
            dp = moveDown(dp) | moveUp(dp) | moveLeft(dp) | moveRight(dp);
        else if (s[i] == 'N') dp = moveUp(dp);
        else if (s[i] == 'E') dp = moveRight(dp);
        else if (s[i] == 'S') dp = moveDown(dp);
        else if (s[i] == 'W') dp = moveLeft(dp);
    }
    cout << dp.count();

    return 0;
}

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