Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
Statistical Charts
Submit Problem
Online Status
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Partition a Matrix
Time Limit: 4000MSMemory Limit: 65536K
Total Submissions: 2516Accepted: 640


Given an M * N matrix consisted of non-negative elements, you may partition it into three parts with two straight line segments. The line segments cannot go through any element of the matrix and they must be parallel to the row or the column of the matrix, but they need not to be parallel to each other. Each of the three parts is a non-empty matrix, which means it contains at least one element. We define the value of a matrix as the sum of all elements in it. We denote the values of the three remaining matrices as X, Y, Z, and the balance degree as |X - Y| + |Y - Z| + |Z - X|, where |.| means the absolute value. Among all ways of partition, there is one, which has the least balance degree. Your task is to decide what the least balance degree is.


The input will consist of several test cases. For each test case, two integers M and N are given in the first line, indicating the number of rows and columns of the matrix; each of the following M lines contains N integers, indicating the matrix. The input is terminated by a single line with two zeros. You may assume that 2 <= M, N <= 500 and all elements of the matrix are integers in the range [0, 65535].

There may be some blank lines between test cases.


For each matrix of the input, print a line containing the least balance degree.

Sample Input

3 3
9 8 7
6 5 4
3 2 1
0 0

Sample Output



The three partitions are: {9, 8}, {6, 5, 3, 2}, {7, 4, 1}, whose values are: 9 + 8 = 17, 6 + 5 + 3 + 2 = 16, 7 + 4 + 1 = 12. The corresponding balance degree is: |17 - 16| + |16 - 12| + |12 - 17| = 10. This is the least balance degree you can get.


POJ Monthly,c0500301036

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator