[*] Sơn các hình chữ nhật.

[ngtuananh1122]

Sơn các hcn
1 bảng hcn phẳng dc chia thành các miền hcn không giao nhau và có các cạnh song song với cạnh của bảng. Người ta muốn sơn các miền hcn này, mỗi miền sẽ dc sơn bằng 1 màu định sẵn. Vì khi sơn có hiện tượng sơn chảy xuống phía dưới nên 1 miền hcn phía dưới chỉ được phép sơn khi mà các miền trên, có ảnh hưởng tới nó đã dc sơn.
Theo ví dụ thì miền 2 chỉ được sơn khi miền 5 và 7 đã sơn xong. Nói 1 cách chính xác: miền A bắt buộc phải sơn sau miền B nếu cả 2 điều kiện sau thỏa mãn:
_ hình chiếu của miền A và miền B trên trục hoành có ít nhất 2 điểm chung.
_ tung độ tâm của miền B lớn hơn tung độ tâm của miền A/
Để sơn tất cả các miền, người ta dùng 1 hệ thống chổi sơn đủ màu sắc, 2 chổi khác nhau có màu khác nhau.
Yêu cầu: Tìm số lần phải thay chổi ít nhất. (tính cả lần đầu tiên bắt đầu sơn).
INP: vào từ file văn bản PAINT.inp
_ Dòng đầu là n – số miền hcn trong bảng.
_ N dòng tiếp theo, dòng I ghi thông tin về miền thứ I gồm 5 số nguyên x1,y1,x2,y2,c theo đúng thứ tự đó (x1,y1) là tọa độ đỉnh trái dưới, (x2,y2) là tọa độ đỉnh phải trên, c là màu cần tô.
OUT: PAINT.out ghi số lần thay chổi ít nhất
Giới hạn: 1<=n<=20;1<=c<=15;0<=xi,yi<=100
VD:INP
7
4 0 6 3 2
0 0 4 2 1
4 3 6 5 1
2 5 6 6 2
2 2 4 5 2
0 4 2 6 1
0 2 2 4 1
OUT: 3
Lưu ý: 60% số test có n<=10;


Bài này mình chưa nghĩ được thuật toán! [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG](

[Ricky1990]

Chẳng có ai post bài nhỉ? Chán thật, nghĩ mãi chưa ra thuật toán làm bài này. T_T

[mcqueen]

Bài này mình mới nghĩ ra thuật toán thế này. Nói về cơ bản thì sẽ là thuật toán loang [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]

Đầu tiên ta có nhận xét, với giới hạn N<=20 ta hoàn toàn có thể "số hoá" các trạng thái của N hình chữ nhật bằng một dãy nhị phân, bit 0 biểu diễn chưa được tô, bit 1 biểu diễn đã được tô.

Ví dụ, với N = 2. Ta có các trạng thái có thể là:
'00' : chưa có hình nào được tô màu
'01' : hình 1 được tô màu, hình 2 chưa được tô
'10' : hình 2 được tô màu, hình 1 chưa được tô
'11' : cả 2 hình đã được tô màu

Ta xây dựng hàm Sum[State , Color] với ý nghĩa là số lần đổi màu sơn cho đến khi đạt trạng thái State với màu hiện tại là Color.

Sau đó thực hiện loang từ Sum[State, Color] sang các Sum[NewState, NewColor] với điều kiện sau:
- Từ State có thể chuyển trực tiếp sang NewState (thực chất là tô màu cho thêm một ô trong tập hình chưa được tô màu ở trạng thái State ta được trạng thái mới NewState - Ô có thể tô thì sẽ là ô nào mà hiện tại không)
- NewColor chính là màu cần dùng để chuyển từ trạng thái State sang trạng thái NewState (thực chất là màu của ô mà mình tô thêm)

Cứ như thế ta sẽ thu được các Sum[FinalState, FinalColor] trong đó FinalState là trạng thái mà tất cả các ô đã được tô, còn FinalColor là một màu trong số C màu ban đầu. So sánh các giá trị Sum[FinalState, FinalColor] tìm ra giá trị nhỏ nhất ta thu được kết quả cần tìm.

Độ phức tạp: O(2^N) cho các trạng thái, O(C) cho các màu, O(N) cho đoạn xét khả năng chuyển được từ trạng thái A sang trạng thái B. Các cái này lồng nhau -> Độ phức tạp O(2^N.C.N) xấp xỉ 320 triệu -> chạy được [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]

À quên, bài này thuật toán nghe thì có vẻ đơn giản nhưng thực ra không phải bài toán dễ cài đặt, vì thế các bạn nào mới học không nên thử sức [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]

[chaydidaubaygio]

THuật toán đọc khó hiểu quá. Anh Trung có thể giải thích kĩ hơn về thuật toán không? Trong quá trình loang làm sao để phân biệt ô nào được phép sơn và ô chưa được sơn? (ô được phép sơn là ô mà những ô bên trên nó đã đúng màu).

[zomplus]

Đây là code mẫu cho bài này, tuy chưa hiểu lắm (bài mẫu của BGK) nhưng mình vẫn post lên để mọi người tham khảo.

Program PAINT;
Const
FI='PAINT.INP';
FO='PAINT.OUT';
Maxn=23;

Type
Hcn=
Record
x1, y1, x2, y2, c, t: longint;
End;

Var
F: Array[0..1 shl maxn, 0..maxn] of longint;
//Tr: Array[0..1 shl maxn, 0..maxn] of longint;
H: Array[0..maxn] of hcn;
N, Re: Longint;
G: Text;

Procedure Enter;
Var
i: longint;
Begin
Assign(g, fi); reset(g);
Readln(g, n);
For i:=1 to n do
With h do readln(g, x1, y1, x2, y2, c);
Close(g);
End;

Function Check(i, j: longint): boolean;
Begin
If (h.x1 >= h[j].x2) or (h.x2 <= h[j].x1) then exit(False);
Exit(h[j].y1 > h.y1);
End;

Procedure Init;
Var
i, j: longint;
Begin
For i:=1 to n do
Begin
H.t:=0;
For j:=1 to n do
if i<>j then If check(i, j) then
h.t:=h.t or (1 shl (j-1));
End;
End;

Function Min(x, y: longint): longint;
Begin
If x<=y then exit(x) else exit(y);
End;

Procedure Solve;
Var
i, j, s, p: longint;
Begin
Init;
Fillchar(f, sizeof(f), 0);

For s:=1 to (1 shl n)-1 do
For i:=1 to n do
If s and (1 shl (i-1))>0 then
Begin
p:=s xor (1 shl (i-1));
If p=0 then
Begin
If h.t=0 then F[s, i]:=1
Else F[s, i]:=n+1;
End
Else
Begin
F[s, i]:=n+1;

If h.t and p = h.t then
For j:=1 to n do
if F[s, i] > F[p, j] + ord(h.c<>h[j].c) then
Begin
F[s, i]:=F[p, j] + ord(h.c<>h[j].c);
//Tr[s, i]:=j;
End;
End;
End
Else F[s, i]:=n+1;

Re:=n+1;
For i:=1 to n do
re:=min(re, f[s, i]);


{i:=1;
Repeat
writeln(tr[s, i]);
j:=s;
s:=s xor (1 shl (i-1));
i:=tr[j, i];
until s=0; }
End;

Procedure Print;
Begin
Assign(g, fo); rewrite(g);
Writeln(g, re);
Close(g);
End;

BEGIN
Enter;
Solve;
Print;
END.

[parkhill]

Giang à, thực chất thuật toán trên là thuật toán QHĐ và có độ phức tạp là O(2^N.C.N). Thuật toán của anh về bản chất thì giống như bài trên, chỉ có khác là anh chọn thuật toán Loang để biểu diễn thôi. Và theo "kinh nghiệm" của anh thì thuật toán loang thường chạy nhanh hơn và dễ hiểu hơn, tuy nhiên cài đặt thì dài hơn [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]

[seoprovu1]

Qhd thì công thức như nào anh? Em chưa hiểu rõ công thức qhd bài này với cả cách loang của anh. [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]