Hướng dẫn giải của Quân hậu

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, sussyboy, lephuochauhungvuong

Hiểu bài toán

Bài toán yêu cầu với mỗi ô trống (không có vật cản) trên bàn cờ m x n, hãy tính xem có bao nhiêu vị trí đặt quân hậu (cũng trên ô trống) sao cho quân hậu tại vị trí đó kiểm soát được ô trống đó. Theo luật cờ vua, quân hậu kiểm soát các ô cùng hàng, cùng cột, và 2 đường chéo chính phụ nếu không gặp vật cản (#) ở giữa. Nói cách khác, ô (i, j) được kiểm soát bởi hậu ở (x, y) nếu:

Cùng hàng (i=x): khoảng cách giữa j và y không có vật cản.
Cùng cột (j=y): khoảng cách giữa i và x không có vật cản.
Đường chéo chính (i - j = x - y): khoảng cách trên đường chéo không có vật cản.
Đường chéo phụ (i + j = x + y): khoảng cách trên đường chéo không có vật cản. Đề bài yêu cầu xuất ra ma trận kết quả, trong đó phần tử (i, j) là số lượng vị trí đặt hậu hợp lệ kiểm soát ô (i, j).

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

Cách Quét liên tục (Sweep Line) - Tính đoạn

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

int main() {
    int m, n;
    cin >> m >> n;
    vector<string> a(m);
    for (int i = 0; i < m; i++) cin >> a[i];

    // row_len[i][j]: số lượng ô '.' liên tiếp trong hàng i tại vị trí j
    vector<vector<int>> row_len(m, vector<int>(n, 0));
    vector<vector<int>> col_len(m, vector<int>(n, 0));
    vector<vector<int>> diag1_len(m, vector<int>(n, 0)); // i - j = const
    vector<vector<int>> diag2_len(m, vector<int>(n, 0)); // i + j = const

    // 1. Xử lý hàng ngang
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; ) {
            if (a[i][j] == '#') { j++; continue; }
            int start = j;
            while (j < n && a[i][j] == '.') j++;
            int len = j - start;
            for (int k = start; k < j; k++) row_len[i][k] = len;
        }
    }

    // 2. Xử lý cột dọc
    for (int j = 0; j < n; j++) {
        for (int i = 0; i < m; ) {
            if (a[i][j] == '#') { i++; continue; }
            int start = i;
            while (i < m && a[i][j] == '.') i++;
            int len = i - start;
            for (int k = start; k < i; k++) col_len[k][j] = len;
        }
    }

    // 3. Xử lý đường chéo chính (i - j = const)
    // Duyệt các đường chéo bắt đầu từ hàng 0 và cột 0
    for (int k = 0; k < m + n - 1; k++) {
        int start_i = (k < n) ? 0 : k - n + 1;
        int start_j = (k < n) ? k : 0;
        int i = start_i, j = start_j;
        while (i < m && j < n) {
            if (a[i][j] == '#') { i++; j++; continue; }
            int s_i = i, s_j = j;
            while (i < m && j < n && a[i][j] == '.') { i++; j++; }
            int len = i - s_i; // hoặc j - s_j
            for (int p_i = s_i, p_j = s_j; p_i < i; p_i++, p_j++) {
                diag1_len[p_i][p_j] = len;
            }
        }
    }

    // 4. Xử lý đường chéo phụ (i + j = const)
    // Duyệt các đường chéo bắt đầu từ hàng 0 (từ cột 0 đến n-1) và cột 0 (từ hàng 1 đến m-1)
    // Đường chéo phụ: i + j = S
    for (int S = 0; S <= m + n - 2; S++) {
        // Điểm đầu: Neu S < n: (0, S), nguoc lai: (S - n + 1, n - 1)
        // Tuy de bai chieu dai nho, ta duyet don gian
        // Bat dau tu hang 0, cot tuong ung
        int start_j = (S < n) ? S : n - 1;
        int start_i = S - start_j;

        int i = start_i, j = start_j;
        while (i < m && j >= 0) {
            if (a[i][j] == '#') { i++; j--; continue; }
            int s_i = i, s_j = j;
            while (i < m && j >= 0 && a[i][j] == '.') { i++; j--; }
            int len = i - s_i;
            for (int p_i = s_i, p_j = s_j; p_i < i; p_i++, p_j--) {
                diag2_len[p_i][p_j] = len;
            }
        }
    }

    // Tính kết quả
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (a[i][j] == '.') {
                // Kết quả là tổng của 4 hướng trừ đi 3 chính nó (vì hậu tại ô đó được đếm 4 lần)
                // Công thức: (row - 1) + (col - 1) + (diag1 - 1) + (diag2 - 1)
                // = row + col + diag1 + diag2 - 4
                cout << (row_len[i][j] + col_len[i][j] + diag1_len[i][j] + diag2_len[i][j] - 4) << " ";
            } else {
                cout << "0 ";
            }
        }
        cout << "\n";
    }
    return 0;
}

Time Complexity: O(m*n)
Space Complexity: O(m*n)

Phương pháp này tối ưu hóa brute force bằng cách chia bài toán thành 4 hướng (hàng, cột, 2 đường chéo). Với mỗi hướng, ta thực hiện quét một lần để xác định các đoạn ô trống liên tiếp (contiguous segments). Sau đó, ta gán độ dài của đoạn đó cho từng ô trong đoạn.

Ví dụ với hàng ngang: Duyệt qua từng hàng, tìm các đoạn liên tiếp các ô '.'.

Nếu gặp '.', ta đánh dấu start, đi tiếp đến khi gặp '#' hoặc hết hàng.
Độ dài đoạn là end - start.
Gán giá trị độ dài này cho tất cả các ô trong đoạn.

Làm tương tự cho cột dọc và 2 đường chéo (cần xử lý traversal cho đường chéo).

Cuối cùng, tại ô (i, j) trống, số lượng hậu kiểm soát nó chính là: row_len[i][j] + col_len[i][j] + diag1_len[i][j] + diag2_len[i][j] - 4 (Số lượng ô hợp lệ ở 4 hướng cộng lại, trừ đi 4 vì ô (i,j) được đếm 4 lần).

Độ phức tạp: O(m*n) cho cả 4 hướng, do mỗi ô chỉ được xử lý constant số lần.

Cách Quét liên tục (Sweep Line) - Duyệt 4 hướng

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

int main() {
    int m, n;
    cin >> m >> n;
    vector<string> a(m);
    for (int i = 0; i < m; i++) cin >> a[i];

    vector<vector<int>> res(m, vector<int>(n, 0));

    // 1. Hang ngang
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; ) {
            if (a[i][j] == '#') { j++; continue; }
            int start = j;
            while (j < n && a[i][j] == '.') j++;
            int len = j - start;
            for (int k = start; k < j; k++) res[i][k] += len;
        }
    }

    // 2. Cot doc
    for (int j = 0; j < n; j++) {
        for (int i = 0; i < m; ) {
            if (a[i][j] == '#') { i++; continue; }
            int start = i;
            while (i < m && a[i][j] == '.') i++;
            int len = i - start;
            for (int k = start; k < i; k++) res[k][j] += len;
        }
    }

    // 3. Duong cheo chinh (i - j = const)
    // Duyet theo duong cheo
    // Duong cheo bat dau tu cot 0 (hang 0 -> m-1)
    for (int start_i = 0; start_i < m; start_i++) {
        int i = start_i, j = 0;
        while (i < m && j < n) {
            if (a[i][j] == '#') { i++; j++; continue; }
            int s_i = i, s_j = j;
            while (i < m && j < n && a[i][j] == '.') { i++; j++; }
            int len = i - s_i;
            for (int p_i = s_i, p_j = s_j; p_i < i; p_i++, p_j++) res[p_i][p_j] += len;
        }
    }
    // Duong cheo bat dau tu hang 0 (cot 1 -> n-1)
    for (int start_j = 1; start_j < n; start_j++) {
        int i = 0, j = start_j;
        while (i < m && j < n) {
            if (a[i][j] == '#') { i++; j++; continue; }
            int s_i = i, s_j = j;
            while (i < m && j < n && a[i][j] == '.') { i++; j++; }
            int len = i - s_i;
            for (int p_i = s_i, p_j = s_j; p_i < i; p_i++, p_j++) res[p_i][p_j] += len;
        }
    }

    // 4. Duong cheo phu (i + j = const)
    // Duong cheo phu bat dau tu hang 0 (cot 0 -> n-1)
    for (int start_j = 0; start_j < n; start_j++) {
        int i = 0, j = start_j;
        while (i < m && j >= 0) {
            if (a[i][j] == '#') { i++; j--; continue; }
            int s_i = i, s_j = j;
            while (i < m && j >= 0 && a[i][j] == '.') { i++; j--; }
            int len = i - s_i;
            for (int p_i = s_i, p_j = s_j; p_i < i; p_i++, p_j--) res[p_i][p_j] += len;
        }
    }
    // Duong cheo phu bat dau tu cot n-1 (hang 1 -> m-1)
    for (int start_i = 1; start_i < m; start_i++) {
        int i = start_i, j = n - 1;
        while (i < m && j >= 0) {
            if (a[i][j] == '#') { i++; j--; continue; }
            int s_i = i, s_j = j;
            while (i < m && j >= 0 && a[i][j] == '.') { i++; j--; }
            int len = i - s_i;
            for (int p_i = s_i, p_j = s_j; p_i < i; p_i++, p_j--) res[p_i][p_j] += len;
        }
    }

    // In ket qua
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (a[i][j] == '.') {
                cout << res[i][j] - 4 << " ";
            } else {
                cout << "0 ";
            }
        }
        cout << "\n";
    }
    return 0;
}

Time Complexity: O(m*n)
Space Complexity: O(m*n)

Đây là cách viết trực quan hơn của phương pháp Sweep Line. Thay vì lưu trữ độ dài vào các mảng phụ rồi cộng lại, ta cộng trực tiếp vào mảng kết quả res.

Ta duyệt 4 vòng lặp chính tương ứng với 4 hướng:

Hàng ngang: Duyệt từng hàng, đếm đoạn.
Cột dọc: Duyệt từng cột, đếm đoạn.
Đường chéo chính: Duyệt theo đường chéo. Ta cần chia làm 2 phần để bao quát hết:
- Bắt đầu từ hàng 0, cột chạy từ 0 đến n-1 (trừ cột 0).
- Bắt đầu từ cột 0, hàng chạy từ 1 đến m-1.
- Trong mỗi đường chéo, ta đếm đoạn liên tiếp và cộng vào res.
Đường chéo phụ: Tương tự đường chéo chính:
- Bắt đầu từ hàng 0, cột chạy từ 0 đến n-1.
- Bắt đầu từ cột n-1, hàng chạy từ 1 đến m-1.

Cuối cùng, duyệt qua res, với ô trống, in ra res[i][j] - 4 (trừ 4 vì ô đó được đếm 4 lần). Với ô vật cản, in 0.

Cách Tối ưu hóa truy vấn theo hàng/cột

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

int main() {
    int m, n;
    cin >> m >> n;
    vector<string> a(m);
    for (int i = 0; i < m; i++) cin >> a[i];

    vector<vector<int>> res(m, vector<int>(n, 0));

    // Precompute using prefix sums logic or direct scanning
    // Hang ngang
    for(int i=0; i<m; ++i) {
        int count = 0;
        for(int j=0; j<n; ++j) {
            if(a[i][j] == '#') count = 0;
            else res[i][j] += ++count;
        }
        count = 0;
        for(int j=n-1; j>=0; --j) {
            if(a[i][j] == '#') count = 0;
            else res[i][j] += count++; // Khong cong them 1 o dau tien (da duoc cong o vong tren)
        }
    }

    // Cot doc
    for(int j=0; j<n; ++j) {
        int count = 0;
        for(int i=0; i<m; ++i) {
            if(a[i][j] == '#') count = 0;
            else res[i][j] += ++count;
        }
        count = 0;
        for(int i=m-1; i>=0; --i) {
            if(a[i][j] == '#') count = 0;
            else res[i][j] += count++;
        }
    }

    // Duong cheo chinh (i - j const)
    // Duong cheo bat dau tu hang 0
    for(int start_j = 0; start_j < n; ++start_j) {
        int count = 0;
        for(int i=0, j=start_j; i<m && j<n; ++i, ++j) {
            if(a[i][j] == '#') count = 0;
            else res[i][j] += ++count;
        }
    }
    // Duong cheo chinh bat dau tu cot 0 (hang tu 1)
    for(int start_i = 1; start_i < m; ++start_i) {
        int count = 0;
        for(int i=start_i, j=0; i<m && j<n; ++i, ++j) {
            if(a[i][j] == '#') count = 0;
            else res[i][j] += count++; // O dau tien da duoc tinh
        }
    }
    // Duong cheo chinh nguoc (di chuyen tu phai sang trai)
    // Can chia nua de dem day du
    for(int start_j = 1; start_j < n; ++start_j) {
        int count = 0;
        for(int i=0, j=start_j; i<m && j>=0; ++i, --j) {
            if(a[i][j] == '#') count = 0;
            else res[i][j] += count++; // O dau tien chua duoc tinh ben duong cheo chinh chieu xuoi
        }
    }
    // ... Logic tương tự cho các hướng còn lại ...

    // Day la code minh hoa cho viec chia de trien khai bang 2 vong lap moi huong
    // De don gian, ta co the su dung 4 vong lap cho 4 huong chinh phu
    // Tuy nhien cach nay de bi nham lan.
    // Phuong an Tot nhat: Dung cach Sweep Line 4 huong nhu o Approach 2.

    return 0;
}

Time Complexity: O(m*n)
Space Complexity: O(m*n)

Đây là một biến thể của cách tiếp cận Sweep Line. Thay vì đếm cả đoạn rồi gán, ta có thể chạy hai lần cho mỗi hướng (một lần từ trái sang phải, một lần từ phải sang trái).

Ví dụ hàng ngang:

Lượt 1 (trái sang phải): res[i][j] = res[i][j-1] + 1 nếu không có vật cản, reset về 0 nếu gặp vật cản.
Lượt 2 (phải sang trái): Tương tự, cộng vào res[i][j].

Tuy nhiên, cách này cẩn thận với các đường chéo để đảm bảo đếm đúng số ô kiểm soát được. Cách tiếp cận Sweep Line (đếm đoạn) như Approach 2 thường dễ hiểu và đảm bảo đúng hơn.

Trong Solution 1 và 2, họ sử dụng mảng phụ row_len, col_len... để lưu độ dài đoạn, cách này tốn bộ nhớ hơn một chút nhưng logic rất rõ ràng: đầu tiên quét để tính độ dài, sau đó quét lại để gán giá trị.

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

Cách tiếp cận	Time	Space	Tên
1	O(m*n)	O(m*n)	Quét liên tục (Sweep Line) - Tính đoạn
2	O(m*n)	O(m*n)	Quét liên tục (Sweep Line) - Duyệt 4 hướng
3	O(m*n)	O(m*n)	Tối ưu hóa truy vấn theo hàng/cột

Bài học kinh nghiệm

Bài toán có tính chất độc lập theo 4 hướng (hàng, cột, 2 đường chéo). Có thể chia nhỏ và chinh phục (Divide and Conquer) theo các hướng này.
Thay vì với mỗi ô đích, duyệt tìm ô nguồn, ta nên duyệt theo hàng/cột/chéo để xác định phạm vi ảnh hưởng của các đoạn trống.
Số lượng ô kiểm soát một ô (i, j) bằng tổng số ô trống trong 4 hướng trừ đi 3 (ô hiện tại được đếm 4 lần).

Lỗi thường gặp

Lầm tưởng rằng bài toán có thể giải bằng ma trận kề hoặc Floyd-Warshall (quá chậm O(N^4) hoặc O(N^3)).
Xử lý sai thứ tự duyệt đường chéo phụ (i+j) dẫn đến truy cập ngoài mảng hoặc tính sai độ dài đoạn.
Quên loại trừ các ô vật cản (#) ra khỏi quá trình tính toán và kết quả đầu ra.
Quên trừ đi 4 đơn vị (ô hiện tại) khi tính tổng.

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.