Hướng dẫn giải của Thắp đèn

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.

Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.

Bạn phải đăng nhập để mở lời giải này.

Đăng nhập

Tác giả: Hiếu Nguyễn, hohoanghai5042011, lephuochauhungvuong, khanghoangle06112009

Hiểu bài toán

Bài toán mô phỏng quá trình di chuyển và bật đèn trong một lưới N×N. Bắt đầu tại ô (1,1) đã sáng, người chơi có thể di chuyển sang các ô kề cạnh (trên, dưới, trái, phải) chỉ nếu ô đó đang sáng. Trại ô (x, y) có thể chứa các công tắc giúp bật đèn các ô khác (c, d). Mục tiêu là tìm số lượng tối đa các ô có thể thắp sáng.

Giải thích chi tiết:

  1. Ban đầu chỉ ô (1,1) sáng.
  2. Khi ở một ô sáng, ta có thể bật tất cả các công tắc tại ô đó để thắp sáng các ô đích.
  3. Ta có thể di chuyển sang các ô lân cận nếu ô đó đang sáng.
  4. Vấn đề nảy sinh khi một ô được thắp sáng nhưng chưa thể đi đến ngay lập tức (do bị ngăn cách bởi các ô tối). Ta cần tiếp tục tìm kiếm khi có các ô mới được thắp sáng và nằm trong vùng có thể đi đến.

Ví dụ: Có thể thắp sáng ô B từ ô A, nhưng ô B bị ngăn cách bởi ô tối C. Nếu sau đó ta thắp sáng ô C (từ nơi khác), ta có thể đi qua C để đến B.

Các cách tiếp cận

Cách BFS Tái thẩm định (Re-running BFS)
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105;
int n, m;
vector<pair<int, int>> switches[MAXN][MAXN];
bool light[MAXN][MAXN];
bool visited[MAXN][MAXN];
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, -1, 0, 1};

bool inGrid(int x, int y) {
    return x >= 1 && x <= n && y >= 1 && y <= n;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        switches[a][b].push_back({c, d});
    }

    int res = 0;
    // Lặp lại BFS cho đến khi không còn thay đổi
    while (true) {
        memset(visited, 0, sizeof(visited));
        queue<pair<int, int>> q;
        q.push({1, 1});
        visited[1][1] = true;

        // BFS để tìm vùng sáng có thể đi tới
        while (!q.empty()) {
            auto [x, y] = q.front(); q.pop();
            for (int d = 0; d < 4; ++d) {
                int nx = x + dx[d], ny = y + dy[d];
                if (inGrid(nx, ny) && !visited[nx][ny] && light[nx][ny]) {
                    visited[nx][ny] = true;
                    q.push({nx, ny});
                }
            }
        }

        // Đếm và bật công tắc
        int old_res = res;
        res = 0;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (visited[i][j]) {
                    res++;
                    // Nếu đang ở ô này, bật tất cả công tắc
                    for (auto sw : switches[i][j]) {
                        if (!light[sw.first][sw.second]) {
                            light[sw.first][sw.second] = true;
                        }
                    }
                }
            }
        }
        if (res == old_res) break;
    }
    cout << res << endl;
    return 0;
}
  • Time Complexity: O(K * N^2 + M), với K là số lần lặp (thường nhỏ)
  • Space Complexity: O(N^2 + M)

Cách tiếp cận này chia bài toán thành các giai đoạn. Mỗi giai đoạn:

  1. Chạy BFS từ (1,1) trên lưới chỉ xét các ô đang sáng và đã được visit. Điều này xác định vùng sáng có thể đi tới hiện tại.
  2. Duyệt qua tất cả các ô trong vùng này, đếm số ô sáng và bật tất cả các công tắc trong các ô đó.
  3. Nếu có ô mới được bật sáng, ta lặp lại giai đoạn 1.

Phương pháp này đảm bảo ta luôn thắp sáng các ô mới và kiểm tra xem có thể đi đến chúng không. Nó đơn giản để hiểu nhưng có thể chậm do phải chạy lại BFS nhiều lần.

Cách BFS Đơn kết hợp Kiểm tra Đèn mới
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105;
int n, m;
vector<pair<int, int>> switches[MAXN][MAXN];
bool light[MAXN][MAXN];
bool visited[MAXN][MAXN];
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, -1, 0, 1};

bool inGrid(int x, int y) {
    return x >= 1 && x <= n && y >= 1 && y <= n;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        switches[a][b].push_back({c, d});
    }

    light[1][1] = true;
    visited[1][1] = true;
    queue<pair<int, int>> q;
    q.push({1, 1});

    int res = 1;

    while (!q.empty()) {
        auto [x, y] = q.front(); q.pop();

        // 1. Bật công tắc tại ô hiện tại
        for (auto [nx, ny] : switches[x][y]) {
            if (!light[nx][ny]) {
                light[nx][ny] = true;
                res++;

                // 2. Kiểm tra nếu ô mới sáng này nằm kề ô đã thăm
                // Nếu có, ta có thể đi vào nó ngay lập tức
                for (int d = 0; d < 4; ++d) {
                    int adjx = nx + dx[d];
                    int adjy = ny + dy[d];
                    if (inGrid(adjx, adjy) && visited[adjx][adjy]) {
                        visited[nx][ny] = true;
                        q.push({nx, ny});
                        break; // Đã vào hàng đợi, không cần check tiếp
                    }
                }
            }
        }

        // 3. Thêm các ô lân cận chưa thăm vào hàng đợi
        for (int d = 0; d < 4; ++d) {
            int nx = x + dx[d], ny = y + dy[d];
            if (inGrid(nx, ny) && !visited[nx][ny] && light[nx][ny]) {
                visited[nx][ny] = true;
                q.push({nx, ny});
            }
        }
    }

    cout << res << endl;
    return 0;
}
  • Time Complexity: O(N^2 + M)
  • Space Complexity: O(N^2 + M)

Đây là thuật toán tối ưu nhất. Ta chỉ cần chạy BFS một lần duy nhất.

Logic:

  • Hàng đợi q lưu trữ các ô đã đến được và đang chờ xử lý.
  • Khi xử lý ô (x, y):
    • Bật tất cả công tắc. Nếu có ô (nx, ny) mới sáng:
      • Ngay lập tức kiểm tra xem (nx, ny) có kề với bất kỳ ô nào đã visit chưa. Nếu có, ta có thể đi vào nó ngay, đánh dấu visit và đẩy vào hàng đợi.
    • Duyệt các ô lân cận của (x, y). Nếu ô lân cận sáng và chưa visit, thì visit và đẩy vào hàng đợi.

Điểm mấu chốt: Việc kiểm tra điều kiện "kề ô đã visit" khi bật công tắc giúp ta không cần phải chạy BFS lại từ đầu. Nếu một ô mới sáng mà không kề ô nào đã visit, nó sẽ được xử lý sau này, khi mà đường đi được mở thông qua các ô khác.

Phân tích độ phức tạp

Cách tiếp cận Time Space Tên
1 O(K * N^2 + M), với K là số lần lặp (thường nhỏ) O(N^2 + M) BFS Tái thẩm định (Re-running BFS)
2 O(N^2 + M) O(N^2 + M) BFS Đơn kết hợp Kiểm tra Đèn mới

Bài học kinh nghiệm

  • Vấn đề có thể mô hình hóa như việc tìm vùng liên thông (Connected Component) trong đồ thị các ô, nhưng các cạnh (đường đi) chỉ tồn tại nếu ô đích đang sáng.
  • Thuật toán BFS chỉ cần chạy 1 lần nếu ta xử lý việc "thêm ô mới vào hàng đợi" ngay tại thời điểm ô đó được thắp sáng và có đường vào.
  • Một ô được coi là "có thể đi vào" nếu nó sáng và có ít nhất một ô lân cận đã được duyệt qua (visited).

Lỗi thường gặp

  • Quên kiểm tra điều kiện light[nx][ny] khi duyệt các ô lân cận trong BFS, dẫn đến việc đi vào ô tối.
  • Trong cách tiếp cận BFS 1 lần, nếu chỉ kiểm tra các ô lân cận của ô hiện tại (x, y) khi bật công tắc, ta có thể bỏ lỡ việc vào ô mới nếu ô mới đó kề một ô đã được xử lý trước đó nhưng không kề ô hiện tại. Do đó, phải check kề tất cả các ô đã visit (hoặc check khi visit ô mới).
  • Lưu ý đánh dấu visited đúng lúc để tránh vào hàng đợi 2 lần.

Bình luận

Please read the guidelines before commenting.

Không có bình luận tại thời điểm này.