Submission #1188066

#TimeUsernameProblemLanguageResultExecution timeMemory
1188066nihatgaribliNautilus (BOI19_nautilus)C++20
66 / 100
1096 ms24132 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...