Thread: Tricky grid joining problem

I have the following problem. Let's say I have a grid of values and that each point in this grid has two values associated with them. The numbers can be any positive number or 0. See figure 1. Now the challenge is to combine these grids so that each individual values has a sum of at least 3.
That is, in the left upper corner: (1,4) can be combined with (6,1) to form (7,5), which is >3 for both values.

- Combinations with closeby cells are preferred
- But I they don't have to be connected

Could anybody help me solve this problem? What kind of approach could I possibly use if I want to (possibly approximately) maximize the amount of cells (ie. each combination should yield cells that don't have values much larger than 3 for each value) and minimize the "area" over which each combination is spread out. I.e., close by combinations are prefered. I realze that there is a trade of between these two aims.

If not a solution, could somebody point me in a direction on how to possibly solve this? Search-words, ideas, theories, similar porblems?

Btw, my actual grid is huge, not anything like the toy example here.

Code:

+---+---+---+---+
|1,4|5,5|1,1|4,5|
+---+---+---+---+
|6,1|0,0|2,2|2,2|
+---+---+---+---+
|5,4|5,5|1,1|0,0|
+---+---+---+---+
|0,1|5,5|6,7|2,5|
+---+---+---+---+

_one_ possible result:

Code:

+---+---+---+---+
|   |5,5|  5,6  |
+7,5+---+---+---+
|       |  4,4  |
+---+---+---+---+
|   |5,5|    3,6|
+5,5+---+---+   +
|   |5,5|6,7|   |
+---+---+---+---+

If you set up your Grid as a Graph data structure, you could modify Dijikstra's algorithm to solve this. You could actually implement a recursive algorithm, starting at a new Vertex after you have satisfied conditions for the Vertex you are starting at. The base cases would include grouping all vertices or attempting to group all vertices but being unable to do so.