The first idea is to check all routes that visit all the houses. This solution has exponential complexity and will yield ~30\%~ of the total number of points. In order to improve this, we observe that we don't need to know the exact route to solve the task.

The given matrix can be viewed as a graph, with nodes corresponding to cells of the matrix and edges representing adjacent cells. Nodes that we will pass through in our route will be a part of some connected component of this graph. Let's assume that we can only use nodes with altitudes from interval ~[l, r]~. We can determine if it's possible to visit all the houses in the reduced graph by checking if some connected component contains all the houses and the starting point. This leads to an ~\mathcal O(N^6)~ solution as we can try out all the possible values for ~l~ and ~r~. This solution is worth ~60\%~ of the total number of points.

We can further improve our solution by observing that if we fix the value of ~l~, we can binary search for the best ~r~. Complexity now becomes ~\mathcal O(N^4 \log N)~ which is enough to obtain full points.

~\mathcal O(N^4)~ solution also exists but we will not discuss it here.