Submission #1106773

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106773		minhvule	Olympiads (BOI19_olympiads)	C++17	0 / 100	1 ms	508 KiB

olympiads

#include <iostream>
#include <vector>
#include <bitset>

using namespace std;

const int MAX_R = 100; // Giới hạn kích thước tối đa của bản đồ
const int MAX_C = 100;
const int DIRS[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; // N, E, S, W

int main() {
    int R, C, M;
    cin >> R >> C >> M;

    vector<string> grid(R);
    for (int i = 0; i < R; i++) {
        cin >> grid[i];
    }

    string signals;
    cin >> signals;

    bitset<MAX_R * MAX_C> reachable; // Bitset để theo dõi các ô có thể đến

    // Duyệt từng ô trong bản đồ để xem đâu là ô sàn có thể là vị trí bắt đầu
    for (int r = 0; r < R; r++) {
        for (int c = 0; c < C; c++) {
            if (grid[r][c] == '.') {
                bitset<MAX_R * MAX_C> current; // Tình trạng hiện tại cho ô bắt đầu
                current.set(r * C + c); // Đánh dấu ô này là có thể đến

                // Xử lý từng tín hiệu
                for (char signal : signals) {
                    bitset<MAX_R * MAX_C> next; // Bitset cho ô tiếp theo

                    if (signal == '?') {
                        // Nếu là '?', thử tất cả 4 hướng
                        for (int dir = 0; dir < 4; dir++) {
                            for (int i = 0; i < MAX_R * MAX_C; i++) {
                                if (current[i]) {
                                    int new_r = (i / C) + DIRS[dir][0];
                                    int new_c = (i % C) + DIRS[dir][1];
                                    if (new_r >= 0 && new_r < R && new_c >= 0 && new_c < C && grid[new_r][new_c] == '.') {
                                        next.set(new_r * C + new_c);
                                    }
                                }
                            }
                        }
                    } else {
                        // Nếu là hướng cụ thể
                        int dir = (signal == 'N') ? 0 : (signal == 'E') ? 1 : (signal == 'S') ? 2 : 3;
                        for (int i = 0; i < MAX_R * MAX_C; i++) {
                            if (current[i]) {
                                int new_r = (i / C) + DIRS[dir][0];
                                int new_c = (i % C) + DIRS[dir][1];
                                if (new_r >= 0 && new_r < R && new_c >= 0 && new_c < C && grid[new_r][new_c] == '.') {
                                    next.set(new_r * C + new_c);
                                }
                            }
                        }
                    }
                    current = next; // Cập nhật trạng thái hiện tại
                }

                // Cập nhật reachable với các ô cuối cùng có thể đến
                reachable |= current;
            }
        }
    }

    // Đếm số ô sàn có thể đến
    int count = 0;
    for (int i = 0; i < R * C; i++) {
        if (reachable[i] && grid[i / C][i % C] == '.') {
            count++;
        }
    }

    cout << count << endl; // Xuất kết quả
    return 0;
}

• Subtask 1: 0 / 13
• Subtask 2: 0 / 31
• Subtask 3: 0 / 24
• Subtask 4: 0 / 32