Bài viết sưu tầm

Một toà lâu đài được mô tả bằng một hình chữ nhật có m*n ô. Giữa các ô có một số bức tưòng ngăn cách chia lâu đài thành các phòng. Như vậy, mỗi phòng tương ứng với tập các ô thông nhau. Tại ô (i,j), cho biết thông tin có tường ngăn giữa ô này với bốn ô kề với nó không bởi giá trị aij là một số nhị phân 4 chữ số tương ứng ô (i,j) có (1) hoặc không có (0) tường ở phía Tây, Bắc, Đông, Nam. Ví dụ aij = 1001 có nghĩa là ô (i,j) có tường ở phía Tây và Nam, nhưng không có tường ở phía Bắc và Đông.  Hãy viết chương trình thực hiện các yêu cầu sau:

a.     Đếm số phòng của toà lâu đài.

b.     Cho biết phòng lớn nhất có diện tích là bao nhiêu ô.

c.     Cho biết nên phá bức tường ngăn hai phòng nào để được một phòng mới có diện tích lớn nhất.

Hương dẫn: Giá trị a_ij có thể nhận tương ứng với số thập phân từ 0 đến 15. Vì vậy ta lưu dữ liệu trong file dạng text có cấu trúc như sau: dòng đầu chứa hai số m,n. Từ dòng thứ hai đến dòng thứ m+1, chứa các hàng của ma trận A = (a_ij). Kết quả đưa ra file dạng text có cấu trúc như sau: dòng đầu chứa số phòng, dònh hai chứa diện tíach phòng lớn nhất và dong ba chứa hàng, cột, hướng của bức tường cần phá.

Chẳng hạn dữ liệu vào là

      4          6

      11        6          11        6          3          10        6

      7          9          6          13        5          15        5

      1          10        12        7          13        7          5

      13        11        10        8          10        12        13

Dữ liệu ra sẽ là:

      5

      9

      4          1          Dong