I can outline. A good solution would need some theorems and proofs and need at least TeX for the typing, and I can't post TeX on HN.
The problem is essentially in the field of 'facility location' which is a topic in essentially optimization.
The problem statement is a mess, so bad we should not even address the problem. But to start to clean up the problem statement, consider the set of all points in the plane, points with coordinates (x,y) where both x and y are integers. Let's call this set of points the 'grid'.
The problem statement mentioned a "grid" but didn't give a solid definition. Bluntly, the people who wrote the problem don't know how to write math. The problem also mentioned "cells", without even defining them. Even we give a definition, we don't need or want "cells". Uh, guys, it is just 100% absolutely, positively necessary to give precise definitions; intuition just doesn't work as a substitute!
So, for some positive integer n, there are n houses at distinct points in the grid.
Now the problem defines a 'distance' on the grid. For grid points P_1 = (x_1, y_1) and P_2 (x_2, y_2), the 'distance' from point P_1 to point P_2 is
d(P_1, P_2) = max(|x_1 - x_2|, |y_1 - y_2|)
Then easily enough,
d( P_1, P_2 ) = d( P_2, P_1 )
If we work at it, then we should be able to confirm that d is a 'metric'. For the main point left to show, that is the triangle inequality. A serious solution would show that we have a metric; e.g., a serious solution has some theorems and proofs and is not just some code. Sorry 'bout that!
Here let's just assume that d is a metric.
Next, let's assume that d can be extended to a metric on all of the plane. Yes, that would take more theorems and proofs.
Next we argue that for points U, V in the plane d(U, V), with V given and fixed, is a convex function in U.
So, what is a 'convex' function? Consider R as the set of real numbers and the plane as the set R^2. Suppose function f: R^2 --> R. Then f is 'convex' provided for all X, Y in R^2 and all t in [0,1],
f(tX + (1-t)Y)
Here tX is multiplying the 'vector' X by the scalar t; similarly for (1 - t)Y. So, convex means, intuitively, that the function value is It's easy to show that every convex function on R^2 is continuous. Maybe in a good solution we should show this!
If f is convex and a >= 0, then af is convex. If f and g are convex, then f + g is convex. So any non-negative linear combination of convex functions is convex.
The 'epigraph' of f is the subset of R^{n + 1}
{ (x, f(x) + a) | a >= 0 }
and is a convex set (yes, I omit the definition of a convex set!). That is we just draw the graph of f and take the surface of the graph and everything above it; we get a convex set. Since f is continuous, this set is closed in the usual topology.
If function f is convex, then there exists linear p: R^2 --> R so that for all h in R^2
f(x + h) >= f(x) + p(h)
So, p is a 'subgradient' of f at x. So, we have a linear function that is thet same as f at x and otherwise is Also, if t > 0 and p(h) >= 0, then
f(x + th) >= f(x) + tp(x)
which means that if we leave point x in direction h following f and find ourselves going uphill, then as we continue in direction h we will continue to go uphill. So, if we want to go downhill, that is, to minimize, then continuing to go uphill won't get us there.
More generally we can show, from a subgradient at x, that there is a line in the plane through x so that one side of the line is downhill and the other side is uphill. So, with several such lines, we can get a convex polyhedron in the plane that has our solution.
Continuing, suppose, for i = 1, 2, ..., n, house i is at point P_i. Then we seek j = 1, 2, ..., n to minimize
S(P_j) = \sum_{i = 1|^n d( P_j, P_i )
(yes, here we are using the syntax of TeX). So, an easy solution is to try each j. For each j, the computational effort is proportional to n so that the whole solution has computational effort proportional to n^2.
We can evaluate S(Q) for any point Q in R^2. Then S(Q) is convex. So, we are trying to minimize a convex function but limited to n given points.
Let's move more quickly now (we'd need some theorems and proofs): We start with a rectangle that covers the n points. We know that our solution is inside this rectangle. This rectangle is a special case of a convex polyhedron. [We assume that the polyhedron has positive area and otherwise handle the case in a different way by a standard unidimensional search.] For such a polyhedron, we can use linear programming to find the center of the largest inscribed circle inside the polyhedron (if the radius is zero, then we know we can change to a unidimensional search). At this point, we find a subgradient of our convex function. This subgradient cuts our polyhedron roughly in half. We pick the half that goes downhill. If there are one or more houses in that half, then we let this half be our new polyhedron. If there is just one house in this half, then that house is our solution and we are done. If that half is empty, then we pick the other half as our polyhedron.
So, this is a 'central cutting plane' algorithm for minimizing a convex function, See Elzinga, Nemhauser, etc.
Okay?