bài toán Aladdin (duyệt tham lam)
Thứ Năm, 25 tháng 6, 2015
Aladdin
Cho tới
nay, Aladdin vẫn còn sống ở đất nước Iraq đau thương. Toàn bộ gia sản,
trong đó có cả cây đèn thần đã bị chiến tranh hủy hoại. Để nuôi mẹ, Aladdin lại
dệt thảm. Một hôm, anh nhận được một đơn đặt hàng dệt một tấm thảm hình vuông
thỏa mãn những điều kiện sau:
§
Thảm gồm N dòng và N cột tạo
thành N × N ô vuông đơn vị. Các ô vuông đơn vị có màu đen hoặc trắng.
§
Với mỗi hình vuông có độ dài cạnh
bằng 2, người ta quy định trước số ô màu đen phải có.
§
Người đặt hàng khẳng định đã từng
nhìn thấy một tấm thảm như vậy.
Input: ALADDIN.INP
§
Dòng đầu ghi số nguyên N.
§
N – 1 dòng sau, mỗi dòng ghi N – 1 số trong phạm vi 0..4.
§
Số thứ V của dòng thứ
U trong N – 1 dòng trên là số ô đen trong hình vuông gồm 4 ô (U,V), (U+1,V),
(U,V+1), (U+1,V+1).
Output: ALADDIN.OUT
Gồm N dòng, mỗi dòng ghi N số 0 hoặc 1 tương ứng
với ô đó không màu trắng hoặc màu đen. Nếu có nhiều kết quả thỏa mãn, chỉ cần
đưa ra một kết quả duy nhất.
Ví dụ:
ALADDIN.INP
|
ALADDIN.OUT
|
4
3
2 3
2
3 3
1
2 1
|
1
1 0 1
1
0 1 1
0
1 1 0
0
0 0 0
|
Giới hạn:
·
1 ≤ N ≤ 200
·
Thời gian: 1s/test
code pascal hay
All comments [ 0 ]
Your comments