Bài toán: P1228 Lấp đầy thảm - Luogu

Hiểu rõ cách tiếp cận bài toán này sẽ giúp bạn giải quyết một cách dễ dàng.

Trước hết, chúng ta chia hình vuông thành bốn vùng: trên-trái, dưới-trái, trên-phải, dưới-phải. Đầu tiên, xác định tọa độ (x, y) nằm ở vùng nào.

Nếu tọa độ nằm ở góc trên-trái, chúng ta đặt một ô vuông ở đường chéo đối diện, tức là vùng dưới-phải.

Tương tự, nếu tọa độ nằm ở các vùng khác, chúng ta cũng đặt một ô vuông ở đường chéo tương ứng. Bằng cách tiếp cận này, chúng ta có thể lấp đầy toàn bộ hình vuông một cách hoàn hảo.

Chúng ta chỉ cần biết thông tin: chỉ số góc trên-trái a, b, chiều dài, và tọa độ vật cản để thực hiện đệ quy. Khi chiều dài bằng 1, chúng ta dừng đệ quy.

Ví dụ: khi x, y nằm ở vùng dưới-phải

if (x >= a+len && y >= b+len)   //x, y nằm trong vùng dưới-phải

Chúng ta đặt một ô vuông ở đường chéo đối diện

    cout << a+len-1 << " " << b+len-1 << " " << 4 << endl;

Lúc này, có bốn vùng con với các điểm bắt đầu khác nhau:

Mỗi điểm bắt đầu góc trên-trái đại diện cho góc trên-trái của vùng tương ứng, giúp chúng ta xác định x, y nằm ở phần tư nào của vùng (vùng được chia thành bốn phần).

Tiếp theo, chúng ta tiến hành đệ quy. Các tham số đầu tiên là tọa độ x, y của góc trên-trái vùng, tham số giữa là chiều dài, và hai tham số cuối là tọa độ vật cản.

    dfs(a+len, b+len, len, x, y);
    dfs(a, b, len, a+len-1, b+len-1);
    dfs(a+len, b, len, a+len, b+len-1);
    dfs(a, b+len, len, a+len-1, b+len);

Chỉ với năm tham số này, chúng ta có thể hoàn thành bài toán một cách hiệu quả thông qua đệ quy.

Nếu bài toán là Special Judge (spj), điều này có nghĩa là không yêu cầu định dạng đầu ra cụ thể.

#include <iostream>

using namespace std;
int kichThuoc;
int soLanChia;
int x, y;

void giaiQuyet(int gTren, int gTrai, int kichThuoc, int x, int y)
{
    if (kichThuoc == 1) return;
    
    kichThuoc /= 2;
    
    if (x < gTren+kichThuoc && y < gTrai+kichThuoc)
    {
        cout << gTren+kichThuoc << " " << gTrai+kichThuoc << " " << 1 << endl;
        giaiQuyet(gTren, gTrai, kichThuoc, x, y);
        giaiQuyet(gTren+kichThuoc, gTrai+kichThuoc, kichThuoc, gTren+kichThuoc, gTrai+kichThuoc);
        giaiQuyet(gTren+kichThuoc, gTrai, kichThuoc, gTren+kichThuoc, gTrai+kichThuoc-1);
        giaiQuyet(gTren, gTrai+kichThuoc, kichThuoc, gTren+kichThuoc-1, gTrai+kichThuoc);
    }
    else if (x >= gTren+kichThuoc && y >= gTrai+kichThuoc)
    {
        cout << gTren+kichThuoc-1 << " " << gTrai+kichThuoc-1 << " " << 4 << endl;
        giaiQuyet(gTren+kichThuoc, gTrai+kichThuoc, kichThuoc, x, y);
        giaiQuyet(gTren, gTrai, kichThuoc, gTren+kichThuoc-1, gTrai+kichThuoc-1);
        giaiQuyet(gTren+kichThuoc, gTrai, kichThuoc, gTren+kichThuoc, gTrai+kichThuoc-1);
        giaiQuyet(gTren, gTrai+kichThuoc, kichThuoc, gTren+kichThuoc-1, gTrai+kichThuoc);
    }
    else if (x >= gTren+kichThuoc)
    {
        cout << gTren+kichThuoc-1 << " " << gTrai+kichThuoc << " " << 3 << endl;
        giaiQuyet(gTren+kichThuoc, gTrai, kichThuoc, x, y);
        giaiQuyet(gTren, gTrai+kichThuoc, kichThuoc, gTren+kichThuoc-1, gTrai+kichThuoc);
        giaiQuyet(gTren, gTrai, kichThuoc, gTren+kichThuoc-1, gTrai+kichThuoc-1);
        giaiQuyet(gTren+kichThuoc, gTrai+kichThuoc, kichThuoc, gTren+kichThuoc, gTrai+kichThuoc);
    }
    else
    {
        cout << gTren+kichThuoc << " " << gTrai+kichThuoc-1 << " " << 2 << endl;
        giaiQuyet(gTren, gTrai+kichThuoc, kichThuoc, x, y);
        giaiQuyet(gTren+kichThuoc, gTrai+kichThuoc, kichThuoc, gTren+kichThuoc, gTrai+kichThuoc);
        giaiQuyet(gTren, gTrai, kichThuoc, gTren+kichThuoc-1, gTrai+kichThuoc-1);
        giaiQuyet(gTren+kichThuoc, gTrai, kichThuoc, gTren+kichThuoc, gTrai+kichThuoc-1);
    }
}

int main()
{
    cin >> soLanChia;
    cin >> x >> y;
    kichThuoc = 1 << soLanChia;
    
    giaiQuyet(1, 1, kichThuoc, x, y);
    
    return 0;
}