Submission #1188066

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188066		nihatgaribli	Nautilus (BOI19_nautilus)	C++20	66 / 100	1096 ms	24132 KiB

nautilus

#include <iostream>
#include <vector>
#include <string>
#include <set>
using namespace std;

int R, C, M;
vector<string> grid;
string signals;

int dx[4] = {-1, 0, 1, 0}; // N, E, S, W
int dy[4] = {0, 1, 0, -1};
char dir[4] = {'N', 'E', 'S', 'W'};

int main() 
{
    cin >> R >> C >> M;
    grid.resize(R);
    for (int i = 0; i < R; i++) {
        cin >> grid[i];
    }
    cin >> signals;

    set<pair<int, int>> positions;

    // Initialize with all water cells
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            if (grid[i][j] == '.') {
                positions.insert({i, j});
            }
        }
    }

    for (int k = 0; k < M; k++) {
        set<pair<int, int>> new_positions;
        char s = signals[k];
        for (auto pos : positions) {
            int x = pos.first;
            int y = pos.second;
            for (int d = 0; d < 4; d++) {
                if (s == '?' || s == dir[d]) {
                    int nx = x + dx[d];
                    int ny = y + dy[d];
                    if (nx >= 0 && nx < R && ny >= 0 && ny < C && grid[nx][ny] == '.') {
                        new_positions.insert({nx, ny});
                    }
                }
            }
        }
        positions = new_positions;
        if (positions.empty()) break; 
    }

    cout << positions.size() << endl;
    return 0;
}

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