Tin 11 : Chuyên đề bồi dưỡng h/s giỏi ....

[hung1xpro96]

[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.

Bài Toán : Miền Liên Thông .
Cho bảng HCN chia thành NxM ô vuông . Mỗi ô vuông ghi 1 số 0 hoặc 1 . Một miền 0 của bảng là tập hợp các ô chung cạnh và chứa số 0 . Địa chỉ của một miền là toạ độ [ dòng , cột ] của ô đầu tiên thuộc miền theo thứ tự duyệt từ trái sang phải , từ trên xuống dưới . Hãy tính số miền 0 và tìm miền 0 có diện tích lớn nhất ( số 0 chứa 0 nhiều nhất ) .

Dữ liệu vào : MLT.INP
-Dòng 1 ghi 2 số N , M (0<N , M<=100)
-N dòng tiếp theo , mỗi dòng gồm N số 0/1 theo thứ tự từ trái sang phải .
Dữ liệu ra : MLT.OUT
-Dòng 1 : Ghi số lượng miền 0 .
-Dòng 2 : Ghi diện tích của miền 0 có diện tích lớn nhất .
- Các dòng tiếp theo , mỗi dòng ghi địa chỉ một miền 0 có diện tích lớn nhất .
P/s : Mọi người làm dùng mình với ( Bài toán giải theo cách dùng ứng dụng lí thuyết đồ thị , dùng duyệt rộng nếu bạn nào rãnh làm cho mình duyệt sâu luôn nha ) Còn về phần vd thì mình thêm sau .----------\\====//---->>>>>
VD :

MLT.INP
4 5
1 0 0 0 1
0 1 0 0 1
1 0 1 1 1
1 0 0 0 0

MLT.OUT
3
5
1 2
3 2

 

[hung1xpro96]

Đệ quy vét cạn quay lui.

Em tham khảo bài toán miền liên thông nhé


gọi tập đỉnh là S
Bước 1 : j=1;
lấy k thuộc S
Sj:={k}
S:=S-{1}
Bước 2 :
for (l là các đỉnh còn lại ) do
begin
if (l có cạnh nối trực tiếp đến các đỉnh trong Sj) then
begin
Sj:=Sj+{l};
S:=S-{l}
end;
end;
Bước 3 :
j:=j+1;
If S<> {} then quay về bước 1
Else thoát
Kết qua (j-1) thanh phần cần tách

-------------- Cảm ơn anh ----------------------