\(y\) 年後に区画 \(v\) が沈んでいるための必要十分条件は、「海からスタートして、標高が \(y\) 以下の区画のみを通って \(v\) に到達できること」です。よって問題は次の通り読み替えられます。
「パスに対するコストを、通った区画の標高の最大値と定める。各 \(i\) について、海からコスト \(i\) 以下で到達できる区画の個数を求めよ」

海を始点としたダイクストラ法により、海から各区画までのパスのコストの最小値を求めることができるので、これを集計することでもとの問題に答えることができます。

実装例(C++)

本質的には公式解説と等価です。