注意到我们可以预处理出每个节点走一步能到达的点，显然不会超过 $4$ 个。

设 $f_{l,r,x,y}$ 为把 $l\sim r$ 合并且最终到达 $(x,y)$ 的最小步数，当做到一个 $(l,r)$ 时进行区间 dp，然后 bfs 更新当前所有 $f$ 值。

这样就可以 $O(n^2wh\log(wh))$ 了，其中 $\log$ 因子来自于 bfs 前的排序：为了保证 bfs 遍历每个点恰好一次，需要先排序，当队列内最短路到达了当前值时再把该点入队。

参考代码。