Input for a solution to matrix problem

[tat2dlady]

I have a problem that I am not sure how to even come up with a solution. So, I was wondering if anyone would have any input to the problem at hand. I have to divide a matrix that is defined by an input file into 2 distinct regions so that the sums of the integers in each region are equal. And also to dicover how many combinations of two distinct regions can be created. For example, the first matrix is defined in a file as:

4 4 // The size of the matrix (a 4x4 matrix)
50 85 9 33
301 46 40 19 // The data in the matrix
105 29 11 12
20 13 23 16

The solution to this problem is:

301, 105
50, 85, 9, 33, 46, 40, 19, 20, 29, 11, 12, 13, 23, 16

Each line adds up to 406.

Each region must contain contiguous integers that can be networked together by following the paths from one integer containing cell to another via shared sides. Shared vertices are not acceptable. Wrap around paths from the edges of the matrices are not allowed and there can only be two regions per combination.

Thanks for any input anyone may have.

[murschech]

Here's an idea for how to partially solve the problem. I'm assuming that this is not for a first course in programming or CS. Specifically, I'm assuming you've studied trees (not just binary trees). If there's a more elementary way to do this problem I'd like to know about it.

Call the matrix M. Each entry in the matrix is contiguous to 2, 3, or 4 other entries. For instance M[1][3] is contiguous to M[1][4], M[1][2] and M[2][3]. You can use a tree structure to find all contiguous regions. Since M[1][1] must be in one region or another you can think of your tree as being rooted at M[1][1]. You can use tree traversal methods to traverse every possible contiguous region and then it's fairly easy to tell which regions have the same sums as their complementary regions. The one difficulty here is that the complementary tree of a contiguous region needn't be contiguous.