Submission #209290

#	Time	Username	Problem	Language	Result	Execution time	Memory
209290		Blerargh	Nautilus (BOI19_nautilus)	C++17	66 / 100	1099 ms	100208 KiB

nautilus

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

#pragma GCC optimize("Ofast")

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> ii;
typedef pair<ld,ld> id;

#define FOR(i, a, b) for(int i=(a); i<=(b); i++)
#define ROF(i, a, b) for(int i=(a); i>=(b); i--)
#define MEM(x, v) memset(x, v, sizeof(x))
#define FILL(x, n, v) fill(x, x+n, v)
#define SORT(x) sort((x).begin(), (x).end())
#define CMPSORT(x, cp) sort((x).begin(), (x).end(), cp)
#define FAST ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

#define f first
#define s second
#define ins insert
#define e emplace
#define eb emplace_back
#define ef emplace_front
#define p push
#define pf push_front
#define pb push_back
#define mp make_pair
#define ub upper_bound
#define lb lower_bound
#define ft front
#define bk back
#define pp pop
#define ppb pop_back
#define ppf pop_front

#define db cout<<"YEET\n";
#define ct(x) cout<<x<<'\n';

const ll MOD = 1e9+7; //998244353
const ll MX = 5e5+5;
const ll INF = 1e18;
const ld PI = acos((ld)-1);

int main(){
    FAST
    ll r, c, m;
    string dirs;
    cin >> r >> c >> m;

    char grid[505][505];
    FOR(i,1,r){
        FOR(j,1,c){
            cin >> grid[i][j];
        }
    }

    cin >> dirs;

    set<ll> checked[505][505];
    queue<tuple<ll,ll,ll> > bfs; //r, c, id
    ll cnt=0;
    ll y[4] = {-1, 0, 1, 0}, x[4] = {0, 1, 0, -1}; //nesw

    FOR(i,1,r){
        FOR(j,1,c){
            if (grid[i][j]=='#') continue;

            bfs.e(i,j,0);
            while (!bfs.empty()){
                ll row, col, idx;
                tie(row, col, idx) = bfs.ft();
                bfs.pp();

                if (checked[row][col].count(idx)) continue;
                else checked[row][col].ins(idx);

                if (idx == m) {
                    cnt++;
                    continue;
                }

                if (dirs[idx] == 'N'){
                    row--;
                    if (!row || grid[row][col]=='#') continue;
                    bfs.e(row,col,idx+1);
                }
                if (dirs[idx] == 'E'){
                    col++;
                    if (col>c || grid[row][col]=='#') continue;
                    bfs.e(row,col,idx+1);
                }
                if (dirs[idx] == 'S'){
                    row++;
                    if (row>r || grid[row][col]=='#') continue;
                    bfs.e(row,col,idx+1);
                }
                if (dirs[idx] == 'W'){
                    col--;
                    if (!col || grid[row][col]=='#') continue;
                    bfs.e(row,col,idx+1);
                }
                if (dirs[idx] == '?'){
                    FOR(k,0,3){
                        ll newrow = row+y[k];
                        ll newcol = col+x[k];
                        if (newrow == 0 || newrow > r || newcol == 0 || newcol > c) continue;
                        if (grid[newrow][newcol]=='#') continue;
                        bfs.e(newrow, newcol, idx+1);
                    }
                }
            }
        }
    }
    cout << cnt;
}

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