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:
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.