Nguồn đề bài: http://vn.spoj.com/problems/ALADDIN/
1. Đề bài ALADDIN spoj
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ó.
Input
Dòng đầu ghi số nguyên N (N<=200) 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
Nếu không có kết quả, in ra “No solution” (không có dấu “”) Ngược lại, in ra 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. Để tránh trường hợp có nhiều kết quả, bạn cần đưa ra tấm thảm thoả mãn: số nhận được khi viết các số a[1,1] a[1,2] a[2,1] a[1,3] a[3,1] a[1,4] a[4,1]… a[1,n] a[n,1] a[2,2] a[2,3] a[3,2] a[2,4] a[4,2]… liên tiếp là nhỏ nhất
Example
Input:
4
3 2 3
2 3 3
1 2 1
Output:
1 0 0 1
1 1 1 1
0 0 1 0
0 1 0 0
2. Hướng dẫn giải ALADDIN spoj – Aladdin
Ở bài này, ta sử dụng thuật toán duyệt quay lui:
ver 1
Thử tất cả các trường hợp rồi kiểm tra, nếu tồn tại a[i,j] <0 hoặc >1 thì đáp án đó k thỏa mãn.
Ver này ta chỉ xét được n tới 10.
ver 2
Gọi mảng ghi số ô đen là b, mảng ghi kết quả là a
Ta để ý: nếu biết 3 ô (u,v), (u+1,v), (u,v+1) thì cũng biết ô (u+1,v+1).
ví dụ: khi ta biết ô a[1,1] , a[1,2], a[2,1] thì ta cũng biết được ô a[2,2] vì a[1,1] + a[1,2] + a[2,1] + a[2,2] = b[1,1]
với test mẫu
cứ như thế, nếu biết được hàng thứ nhất và cột thứ nhất thì cũng sẽ biết được cả bảng
=> Do đó, trong ver 2, ta chỉ thử 1 hàng đầu tiên và 1 cột đầu tiên rồi tính các ô còn lại.
ver 3
Ở ver 3, ta chỉ cải tiến hơn ver 2 một chút để có thể duyệt tới n=200, đó là ta thử lần lượt
a[1,1], a[1,2], a[2,1] rồi tìm a[2,2]; ( nếu a[2,2] <0 hoặc >1 thì k thỏa mãn, loại)
a[1,3], a[3,1] rồi tìm a[2,3], a[3,2], a[3,3]; ( nếu a[2,2] , a[2,3] hoặc a[3,2] <0 hoặc >1 thì k thỏa mãn, loại)
….
3. Code tham khảo ALADDIN spoj – Aladdin
Ta có code của ver 3 như sau: (bạn nên tự làm trước khi xem :))) )
#include <bits/stdc++.h>
using namespace std;
int n;
int a[202][202], x[202][202];
bool OK, l = true;
void xuli()
{
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
cout << x[i][j] << " ";
cout << "\n";
}
OK = true;
}
void thu(int k)
{
if (k > n) { xuli(); return; }
for (int i = 0; i <= 1; i++)
for (int j = 0; j <= 1; j++)
{
x[1][k] = i;
x[k][1] = j;
for (int p = 2; p <= k - 1; p++)
{
x[p][k] = a[p - 1][k - 1] - x[p - 1][k] - x[p - 1][k - 1] - x[p][k - 1];
if (x[p][k] < 0 || x[p][k] > 1)
{ l = false; break; }
}
for (int p = 2; p <= k; p++)
{
x[k][p] = a[k - 1][p - 1] - x[k - 1][p] - x[k - 1][p - 1] - x[k][p - 1];
if (x[k][p] < 0 || x[k][p] > 1)
{ l = false; break; }
}
if (l == true) thu(k + 1);
if (OK) return;
l = true;
}
}
int main()
{
OK = false;
//freopen("aladdin.inp","r",stdin);
//freopen("aladdin.out","w",stdout);
cin >> n;
for (int i = 1; i <= n - 1; i++)
for (int j = 1; j <= n - 1; j++)
cin >> a[i][j];
for (int i = 0; i <= n; i++)
for (int j = 0; j <= n; j++)
x[i][j] = 0;
x[1][1] = 0;
thu(2);
if (!OK)
{
for (int i = 0; i <= n; i++)
for (int j = 0; j <= n; j++)
x[i][j] = 0;
x[1][1] = 1;
thu(2);
}
if (!OK) cout << "No solution";
}
