제출 #1187873

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1187873		jamalzadeh	Nautilus (BOI19_nautilus)	C++20	29 / 100	1096 ms	840 KiB

nautilus

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

const int MAXI = 501;
int x, y, m;
vector grid(MAXI, vector<char>(MAXI));
bool dp[MAXI][MAXI][4] = {};
string rotations;

bool go(int i, int j, int dx, int dy, int step) {
    int ni = i + dx, nj = j + dy;
    if (ni < 0 || nj < 0 || ni >= x || nj >= y) return false;
    if (grid[ni][nj] == '#') return false;
    if (step == rotations.size()) return true;

    char r = rotations[step];

    if (r == '?') {
        bool ok = false;
        if (dp[ni][nj][0]) ok |= go(i, j, dx - 1, dy, step + 1);
        if (dp[ni][nj][1]) ok |= go(i, j, dx, dy + 1, step + 1);
        if (dp[ni][nj][2]) ok |= go(i, j, dx + 1, dy, step + 1);
        if (dp[ni][nj][3]) ok |= go(i, j, dx, dy - 1, step + 1);
        return ok;
    }

    if (r == 'N' && dp[ni][nj][0]) return go(i, j, dx - 1, dy, step + 1);
    if (r == 'E' && dp[ni][nj][1]) return go(i, j, dx, dy + 1, step + 1);
    if (r == 'S' && dp[ni][nj][2]) return go(i, j, dx + 1, dy, step + 1);
    if (r == 'W' && dp[ni][nj][3]) return go(i, j, dx, dy - 1, step + 1);

    return false;
}

int main() {
    cin >> x >> y >> m;
    for (int i = 0; i < x; i++)
        for (int j = 0; j < y; j++)
            cin >> grid[i][j];

    cin >> rotations;
    
    for (int i = 0; i < x; i++) {
        for (int j = 0; j < y; j++) {
            if (grid[i][j] == '#') continue;
            if (i > 0     && grid[i - 1][j] != '#') dp[i][j][0] = true;
            if (j < y - 1 && grid[i][j + 1] != '#') dp[i][j][1] = true;
            if (i < x - 1 && grid[i + 1][j] != '#') dp[i][j][2] = true;
            if (j > 0     && grid[i][j - 1] != '#') dp[i][j][3] = true;
        }
    }

    int ans = 0;
    for (int i = 0; i < x; i++) {
        for (int j = 0; j < y; j++) {
            if (grid[i][j] == '.') {
                if (go(i, j, 0, 0, 0)) {
                    ans++;
                }
            }
        }
    }

    cout << ans << endl;
}

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