Hiểu bài toán

Yêu cầu vẽ một bàn cờ vua kích thước n x n, với ô đầu tiên ở góc trên bên trái là ô trắng (W). Các ô màu đen (B) và trắng được tô xen kẽ theo hàng và cột. Nói cách khác, tại vị trí (i, j) (0-indexed), màu sắc phụ thuộc vào tính chẵn lẻ của tổng i + j.

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

Cách Sử dụng chuỗi lặp lại (String Repetition)

#include <iostream>
#include <string>

using namespace std;

int main() {
    int n;
    cin >> n;

    string row1, row2;
    for (int j = 0; j < n; j++) {
        if (j % 2 == 0) {
            row1 += 'W';
            row2 += 'B';
        } else {
            row1 += 'B';
            row2 += 'W';
        }
    }

    for (int i = 0; i < n; i++) {
        if (i % 2 == 0) cout << row1 << "\n";
        else cout << row2 << "\n";
    }

    return 0;
}

• Time Complexity: O(n^2)
• Space Complexity: O(n)

Phương pháp này dựa trên quan sát rằng bàn cờ chỉ có 2 loại hàng lặp lại xen kẽ. Ta xây dựng hai chuỗi row1 (bắt đầu bằng 'W') và row2 (bắt đầu bằng 'B') có độ dài n. Sau đó, duyệt qua các hàng từ 0 đến n-1, in row1 nếu hàng chẵn và row2 nếu hàng lẻ. Việc xây dựng chuỗi mất O(n), in ra từng hàng mất O(n), và có n hàng nên tổng thể tích phức tạp là O(n^2).

Cách Công thức tổng chỉ số (Parity Check)

#include <iostream>

using namespace std;

int main() {
    int n;
    cin >> n;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if ((i + j) % 2 == 0)
                cout << "W";
            else
                cout << "B";
        }
        cout << endl;
    }

    return 0;
}

• Time Complexity: O(n^2)
• Space Complexity: O(1)

Đây là cách tiếp cận trực tiếp và gọn gàng nhất. Màu sắc của ô tại hàng i, cột j được quyết định bởi t tổng i + j. Nếu t tổng là số chẵn, ô đó là 'W' (vì ô (0,0) là 'W'). Nếu t tổng là số lẻ, ô đó là 'B'. Ta chỉ cần lồng 2 vòng lặp để duyệt qua từng ô và in ký tự tương ứng. Phương pháp này không cần lưu trữ thêm chuỗi nào.

Cách Duyệt theo hàng và đảo ngược

#include <iostream>
#include <string>

using namespace std;

int main() {
    int n;
    cin >> n;

    string s = "";
    for (int j = 0; j < n; j++) {
        s += (j % 2 == 0) ? "W" : "B";
    }

    for (int i = 0; i < n; i++) {
        if (i % 2 == 0) cout << s << "\n";
        else {
            for (char c : s) cout << (c == 'W' ? 'B' : 'W');
            cout << "\n";
        }
    }

    return 0;
}

• Time Complexity: O(n^2)
• Space Complexity: O(n)

Phương pháp này xây dựng một chuỗi hàng cơ bản bắt đầu bằng 'W'. Với các hàng chẵn, in chuỗi cơ bản đó. Với các hàng lẻ, ta duyệt qua chuỗi cơ bản, in ra ký tự đối lập ('W' thành 'B' và ngược lại). Cách này cũng hiệu quả nhưng code phức tạp hơn một chút so với việc tạo sẵn 2 chuỗi.

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

Bài học kinh nghiệm

• Màu sắc ô cờ phụ thuộc vào tính chẵn lẻ của t tổng chỉ số hàng và cột (i + j).
• Bàn cờ có tính lặp lại theo hàng: hàng chẵn giống nhau, hàng lẻ giống nhau và khác hàng chẵn.

Lỗi thường gặp

• Sai lệch màu sắc nếu tính toán công thức sai (ví dụ chỉ xét i % 2 hoặc j % 2 riêng lẻ mà không xét tổng).
• Lỗi in thừa dấu cách hoặc ký tự xuống dòng ở cuối cùng (trong problem này in endl sau mỗi dòng là đúng).