# C: Safe Houses

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

{% hint style="warning" %}
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.
{% endhint %}

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