Thuật toán loang

[quanghero100]

[TẶNG BẠN] TRỌN BỘ Bí kíp học tốt 08 môn
Chắc suất Đại học top - Giữ chỗ ngay!!

ĐĂNG BÀI NGAY để cùng trao đổi với các thành viên siêu nhiệt tình & dễ thương trên diễn đàn.

Cho một lưới ô vuông gồm M dòng, N cột. Ở mỗi ô của lưới chỉ chứa số 0 hoặc 1. Mỗi ô vuông được xác định bởi cặp số (x; y) trong đó x là tọa độ dòng, y là tọa độ cột. Từ mỗi ô vuông có thể di chuyển sang ô vuông chung cạnh. Một vùng là một tập hợp các ô vuông kề cạnh với nhau và có giá trị bằng nhau. Các ô vuông kề cạnh với vùng và có giá trị khác với giá trị các ô trong vùng thì không thuộc vùng đó.
Ví dụ: Hình dưới đây là một lưới ô vuông 4 x 6. Hai ô (1; 2) và (3; 4) thuộc cùng một vùng. Hai ô (2; 3) và (1; 6); (1; 2) và (1; 3) là không cùng thuộc một vùng.
1 1 0 0 1 1
0 1 1 0 0 1
0 0 1 1 0 0
1 1 0 0 0 0
Yêu cầu: Cho trước hai ô vuông (x1; y1) và (x2; y2). Hãy cho biết hai ô vuông này có thuộc cùng một vùng hay không.
Tên file bài làm: BAI2.PAS
Dữ liệu vào: Cho trong file BAI2.INP, gồm nhiều dòng:
+ Dòng đầu tiên ghi 2 số M, N (1 ≤ M  100, 1 ≤ N  100).
+ M dòng tiếp theo, mỗi dòng ghi N số 0 hoặc 1 tương ứng với giá trị các ô.
+ Các dòng tiếp theo, mỗi dòng ghi 4 số x1, y1, x2, y2 là hai cặp tọa độ của hai ô vuông cần kiểm tra thuộc hay không thuộc một vùng (1 ≤ x1, y1, x2, y2  100)
(các số trên cùng một dòng ghi cách nhau ít nhất một dấu cách)
Dữ liệu ra: Ghi vào file BAI2.OUT, gồm nhiều dòng. Mỗi dòng ghi một số nguyên, nếu hai ô thuộc cùng một vùng thì ghi số 1; hai ô không cùng thuộc một vùng thì ghi số 2.
Ví dụ:
BAI2.INP
4 6
1 1 0 0 1 1
0 1 1 0 0 1
0 0 1 1 0 0
1 1 0 0 0 0
1 2 3 4
2 3 1 6
BAI2.OUT
1
2

 

[quanghero100]

Oh yeah cuối cùng cũng đã làm ra mọi người xem thử nhé

uses crt;
var a,c:array[1..100,1..100] of integer;
    b:array[1..100,1..100] of boolean;
    i,j,x1,x2,y1,y2,n,m:integer;
    f1,f2:text;
procedure loang1(x,y:integer);
begin
 if a[x,y]=1 then
   begin
     a[x,y]:=0;
     b[x,y]:=false;
     if x>1 then loang1(x-1,y);
     if y>1 then loang1(x,y-1);
     if x<m then loang1(x+1,y);
     if y<n then loang1(x,y+1);
   end;

end;
procedure loang2(x,y:integer);
begin
  if a[x,y]=0 then
    begin
     a[x,y]:=1;
     b[x,y]:=false;
     if x>1 then loang2(x-1,y);
     if y>1 then loang2(x,y-1);
     if x<m then loang2(x+1,y);
     if y<n then loang2(x,y+1);
   end;
end;
begin
  assign(f1,'BAI1.INP');
  reset(f1);
  assign(f2,'BAI2.OUT');
  rewrite(f2);
  readln(f1,m,n);
  for i:=1 to m do
    begin
      for j:=1 to n do
        read(f1,a[i,j]);
        readln(f1);
    end;
  c:=a;
  while not eof(f1) do
    begin
       readln(f1,x1,y1,x2,y2);
       a:=c;
       fillchar(b,sizeof(b),true);
       if a[x1,y1]=1 then loang1(x1,y1)
       else loang2(x1,y1);
       if b[x2,y2]=false then writeln(f2,1) else writeln(f2,2);
    end;
  close(f1);
  close(f2);
end.

 

[cuong276]

này! Anh Quang nói rõ lại đề bài và thuật toán cho em được không? Đề này em không hiểu cho lắm. Anh nói lại cả thuật toán nữa nha.

 

[starlove_maknae_kyuhyun]

về thuật toán bạn có thể tham khảo trong cuốn giải thuật và lập trình của Lê minh hoàng ! rất hay !
hiện giờ anh cũng mất file rồi ! có gì bạn liên hệ với hungxpro hoặc quangherro xem sao ! còn k được thì pm nick lvtpro_96 tớ sẽ nhờ bạn tớ tìm lại

còn về thuật toán loang theo hàng đợi sẽ tối ưu hóa hơn ! và bạn tham khảo lời giả của bạn hungxpro
click

 

[quanghero100]

này! Anh Quang nói rõ lại đề bài và thuật toán cho em được không? Đề này em không hiểu cho lắm. Anh nói lại cả thuật toán nữa nha.

Đề đó là rõ lắm rùi bạn à giờ mình biết giải thích gì thêm đây Mình trích nguyên cái đề bài trong đề thi lun ròi á
Còn về thuật toán thì mình dùng thuật toán loang và trong quá trình loang có đánh dấu quá trình loang để tiện việc kiểm tra xem ô thứ hai có nằm trong miền vừa loang hay không
Ở bài này mình viết thuật loang đệ quy, tuy nhiên mình thấy nó vẫn rất tối ưu rồi không cần dùng ngăn xếp đâu
Trong chương trình chính thuật loang không phải loang hết ma trận mà chỉ loang để đánh dấu vùng chứa ô đầu thôi

 

[concanhcam]

Loang từ ô đầu

+ nếu thấy ô cuối --> 1

+ nếu hết 1 phần ---> 2

 

[faq21106]

Chương trình của bạn Quang sau khi thực hiện cặp ô thứ nhất (1;2) và (3;4) thì giá trị các ô trong ma trận đã thay đổi, dẫn đến kết quả khi loang trên cặp ô thứ hai (2;3) (1;6) sẽ không chính xác. Mình nghĩ cũng không cần phải dùng tới 2 chương trình con loang1 và loang2 cho 2 giá trị 1 và 0 ở mỗi ô. Theo mình nên làm như sau, nhớ giá trị ô (x1,y1), c:=a[x1,y1]. Sau khi loang qua ô nào thì thay đổi giá trị ô đó bằng lệnh a[x,y]:=1-c, nếu ô có giá trị 1 thì nó sẽ thành 0 và ngược lại, sau khi loang xong thì gán giá trị ban đầu lại cho ô. Và có thể không dùng biến b mà chỉ cần dùng biến kq kiểu boolean là được, trong khi loang thì kiểm tra xem ô loang tới có phải là ô (x2,y2) không, nếu phải thì kq:=true.

c:=a[x1,y1]; kq:=false;
procedure loang(x,y:byte);
begin
if (x in[1..n]) and (y in[1..m]) and (a[x,y]=c) then {Nếu ô vẫn chưa ra ngoài ma trận và có giá trị bằng ô (x1,y1) thì loang}
if (x=x2)and(y=y2) then begin kq:=true; exit; end {Nếu ô loang tới là (x2,y2) thì kq là true và kết thúc}
else begin a[x,y]:=1-c;
loang(x+1,y); loang(x-1,y); loang(x,y-1); loang(x,y+1);
a[x,y]:=c;{trả lại giá trị ban đầu của ô (x,y) }
end;
end;

Có gì sai sót mong các bạn góp ý!

 

[quanghero100]

Chương trình của bạn Quang sau khi thực hiện cặp ô thứ nhất (1;2) và (3;4) thì giá trị các ô trong ma trận đã thay đổi, dẫn đến kết quả khi loang trên cặp ô thứ hai (2;3) (1;6) sẽ không chính xác. Mình nghĩ cũng không cần phải dùng tới 2 chương trình con loang1 và loang2 cho 2 giá trị 1 và 0 ở mỗi ô. Theo mình nên làm như sau, nhớ giá trị ô (x1,y1), c:=a[x1,y1]. Sau khi loang qua ô nào thì thay đổi giá trị ô đó bằng lệnh a[x,y]:=1-c, nếu ô có giá trị 1 thì nó sẽ thành 0 và ngược lại, sau khi loang xong thì gán giá trị ban đầu lại cho ô. Và có thể không dùng biến b mà chỉ cần dùng biến kq kiểu boolean là được, trong khi loang thì kiểm tra xem ô loang tới có phải là ô (x2,y2) không, nếu phải thì kq:=true.

Có gì sai sót mong các bạn góp ý!

Bài mình không phải là sẽ bị sai khi loang lần 2 hay 3,...đâu tại mình có dùng mảng c để lưu lại dữ liệu lấy vào rồi mà mà bài đó lúc trước làm vội nên mới viết 2 thủ tục loang như thế nếu như sửa lại thì chỉ cần dùng một hàm loang(x,y,k) là dc thui à Thân!!!!