C: Safe Houses

https://open.kattis.com/problems/safehouses

• For every house-spy pair with coordinates $(x_h,y_h)$and $(x_s,y_s)$, calculate the distance as $|x_h-x_s| + |y_h-y_s|$. All pairwise distances can be computed this way in quadratic time.

Note that if the size of the grid is $N\times N$, there are at most $\mathcal{O} (N^2)$houses and spies. So, computing all pairwise distances can be done in $\mathcal{O} (N^4)$, which is fast enough to fit in the time limit.

• Now, for each spy, compute the distance to the closest house. Report the minimum such value.