oj.uz

Submission #1106773

# Submission time Handle Problem Language Result Execution time Memory
1106773 2024-10-31T04:07:32 Z minhvule Olympiads (BOI19_olympiads) C++17
0 / 100
 1 ms 508 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 508 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB Output isn't correct
2 Halted 0 ms 0 KB -