REPAIR (MS0035)MỘT CÔNG XƯỞNG CÓ CẤU TRÚC HÌNH CHỮ NHẬT ĐƯỢC CHIA THÀN...

Bài 2: REPAIR (MS0035)Một công xưởng có cấu trúc hình chữ nhật được chia thành M ô vuông hàng dọc và N ô vuông hàng ngang (MxN). Các ô vuông có thể có các bức tường dọc theo đường biên của nó theo hướng đông (D),tây (T), nam (N), bắc (B). phòng được giới hạn bởi các bức tường của ô vuông gộp lại.Một nhà thầu được mời đến sửa chữa công xưởng với yêu cầu: Chỉ được phá bỏ một bức tường của ô vuông nào đó để tạo thành một phòng mới có diện tích lớn nhất trong số các phòng của công xưởng sau khi sửa chữa.Dữ liệu vào: Tập tin văn bản REPAIR.INP+ Dòng đầu tiên hai số nguyên dương M và N (0≤M,N≤50)+ Mỗi dòng tiếp theo, mỗi dòng có N số p (0≤p≤15). Số p biểu thị cho số ô vuông tương ứng có bao nhiêu bức tường xung quanh. Số p là tổng của: 1 (nếu có tường ở phía T)2 (Nếu có tường ở phía B4 (nếu có tường ở phía D)8 (nếu có tường ở phía N)Dữ liệu ra: Tập tin văn bản REPAIR.OUT+ Dòng đầu tiên: Số lượng phòng của công xưởng trước khi sửa chữa+ Dòng thứ 2: Diện tích của phòng lớn nhất trước khi sửa chữa+ Nếu phá bỏ một bức tường thì dòng thứ 3 ghi diện tích của phòng lớn nhất sau khi sửa chữa, nếu giữnguyên thì dòng thứ 3 ghi số 0

Ví dụ:

REPAIR.INP REPAIR.INP REPAIR.INP REPAIR.INP4 75111 6 11 6 3 10 693 2 2 2 2 2 6287 9 6 13 5 15 5161 0 0 4 1 0 401 10 12 7 13 7 513 11 10 8 10 12 139 8 8 12 9 8 12Hướng dẫn:Ta thấy rằng các giá trị từ 0 đến 15 tương ứng các xâu nhị phân 4 Bit (0000 đến 1111) với quy định+ Nếu bằng 1 là có tường, bằng 0 là không có tường+ Bit thứ 1 là tường phía Nam+ Bit thứ 2 là tường phía Đông+ Bit thứ 3 là tường phía Bắc+ Bit thứ 4 là tường phía Tây (Chỉ số của Bit tính từ trái qua phải)Ví dụ 1 ô có giá trị 11

10

=1011

2

có nghĩa là ô đó có 3 bức tường ở phía N, B và TÔ có giá trị 14

2

=1110

2

có nghĩa là ô đó có 3 bức tường ở phía T, B và DNhư vậy thay vì lưu các con số ở mỗi ô ta sẽ lưu các dãy xâu nhị phân 4 bitThuật Toán: Đệ quyMảng Z dùng để lưu giá trị của ô x,yPROCEDURE TRY(x,y); {Ô x,y đang được thăm}BEGIN Chon[x,y]:=true; {đánh dâu ô x,y đã được chọn để không thăm lại}INC(dem);If Z[x,y][1]=0 then Try(x,y+1);If Z[[x,y][2]=0 then Try(x+1,y);If Z[[x,y][3]=0 then Try(x,y-1);If Z[[x,y][4]=0 then Try(x-1,y);END;Để chuyển giá trị của ô (x,y) từ số sang xâu nhị phân ta chỉ cần đổi sang nhị phân bình thườngFor i:=1 to N do For j:=1 to N do Z[i,j]:=Doi_so_sang_xau_nhi_phan(A[i,j]);TRƯỜNG THPT CHUYÊN NGUYỄN THƯỢNG HIỀN – TPHCM