Submission #449948

#	Time	Username	Problem	Language	Result	Execution time	Memory
449948		zxcvbnm	Nautilus (BOI19_nautilus)	C++14	66 / 100	1093 ms	135256 KiB

nautilus

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
using ll = long long;
char mat[505][505];
bool vis[5005][505][505];
int n, m, k;
string str;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
#define NORTH 0
#define EAST 1
#define SOUTH 2
#define WEST 3
bool isValid(int x, int y) {
    if (x >= n || x < 0 || y >= m || y < 0) return false;
    if (mat[x][y] == '#') return false;
    return true;
}
void go(int curr, int x, int y) {
    if (!isValid(x, y) || vis[curr][x][y]) return;
    vis[curr][x][y] = true;
    if (curr == k) return;

    if (str[curr] == '?') {
        for(int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (isValid(nx, ny)) {
                go(curr+1, nx, ny);
            }
        }
    } else {
        switch(str[curr]) {
        case 'N':
            go(curr+1, x+dx[NORTH], y+dy[NORTH]);
            break;
        case 'E':
            go(curr+1, x+dx[EAST], y+dy[EAST]);
            break;
        case 'S':
            go(curr+1, x+dx[SOUTH], y+dy[SOUTH]);
            break;
        case 'W':
            go(curr+1, x+dx[WEST], y+dy[WEST]);
            break;
        }
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m >> k;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            cin >> mat[i][j];
        }
    }
    cin >> str;

    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            go(0, i, j);
        }
    }

//    for(int p = 0; p <= k; p++) {
//    if (p != 0) cout << str[p-1] << "\n";
//
//    for(int i = 0; i < n; i++) {
//        for(int j = 0; j < m; j++) {
//            cout << vis[p][i][j] << "";
//        }
//        cout << "\n";
//    }
//    cout << "\n";
//    }

    int cnt = 0;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            cnt += vis[k][i][j];
        }
    }
    cout << cnt << "\n";
    return 0;
}

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