3 ĐIỂM TÊN FILE BÀI LÀM
Bài 4: 3 điểm Tên file bài làm: BAI4.PAS
Cho lưới m×n ô vuông (m, n ≤ 20), các ô được đánh số từ 1 đến m theo chiều từ trên xuống
dưới và đánh số từ 1 đến n từ trái qua phải. Trong mỗi ô cho trước một số tự nhiên (xem hình
minh họa).
7
1 3 5
12 2 5
9 2 10
Yêu cầu: Hãy tìm cách chia lưới trên làm hai miền (chia theo các cạnh của các ô vuông) sao cho
độ lệch của tổng các số thuộc mỗi miền là nhỏ nhất. (Chú ý một miền bao gồm các ô kề cạnh
nhau; cách chia miền có thể không giống nhau, nhưng độ lệch tổng các số thuộc mỗi miền ứng với
mỗi bộ dữ liệu phải giống nhau.)
Dữ liệu: Vào từ file BAI4.INP có cấu trúc như sau:
- Dòng đầu tiên gồm 2 số tự nhiên m, n là kích thước của ô lưới (m là số dòng, n là số cột của
lưới).
- m dòng tiếp theo, mỗi dòng gồm n số tự nhiên 2 byte, mỗi số viết cách nhau ít nhất một dấu cách,
ô nào không có giá trị được coi là bằng 0.
Kết quả: Ghi ra file BAI4.OUT có cấu trúc như sau:
- Dòng đầu ghi 3 số T, T
1
, T
2