htn_spt
08-12-2009, 16:37
Nhờ mọi người cho ý tưởng giải quyết bài toán sau (nếu có chương trình hoàn chỉnh thì càng tốt). Cảm ơn mọi người!
Đề bài:
Bài tập chia lưới
Cho lưới m x n ô vuông (m, n <=10), 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
Yêu cầu: Hãy tìm cách chia lưới trên thành 2 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ố 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 BAITAP.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 nhỏ hơn hoặc bằng 50, mỗi số viết cách nhau 1 dấu cách, ô nào không có giá trị được coi là bằng 0
Kết quả: Ghi ra file BAITAP.OUT có cấu trúc như sau:
- Dòng đầu ghi 3 số T, T1, T2 tương ứng là: tổng giá trị các số trên toàn lưới, tổng giá trị các số thuộc miền thứ nhất, tổng giá trị các số thuộc miền thứ hai
- m dòng sau, mỗi dòng ghi n số 0 hoặc 1 miêu tả lưới sau khi đã chia thành 2 miền, trong đó các số 0 kí hiệu cho các ô thuộc miền thứ nhất, các số 1 kí hiệu cho các ô tương ứng thuộc miền thứ 2
Đề bài:
Bài tập chia lưới
Cho lưới m x n ô vuông (m, n <=10), 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
Yêu cầu: Hãy tìm cách chia lưới trên thành 2 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ố 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 BAITAP.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 nhỏ hơn hoặc bằng 50, mỗi số viết cách nhau 1 dấu cách, ô nào không có giá trị được coi là bằng 0
Kết quả: Ghi ra file BAITAP.OUT có cấu trúc như sau:
- Dòng đầu ghi 3 số T, T1, T2 tương ứng là: tổng giá trị các số trên toàn lưới, tổng giá trị các số thuộc miền thứ nhất, tổng giá trị các số thuộc miền thứ hai
- m dòng sau, mỗi dòng ghi n số 0 hoặc 1 miêu tả lưới sau khi đã chia thành 2 miền, trong đó các số 0 kí hiệu cho các ô thuộc miền thứ nhất, các số 1 kí hiệu cho các ô tương ứng thuộc miền thứ 2