以下では、上から \(i\) 番目かつ左から \(j\) 番目の区画を \((i,j)\) で表し、現在から \(k\) 年後を \(k\) 年目と表現します。
また、以下では、区画が「海または海に沈んだ区画に上下左右に隣接する」ことを単に「海に接する」と表現します。

区画 \((i,j)\) が海に沈むタイミングは次の \(2\) つしかありません。

• 海に接している状態で \(A_{i,j}\) 年目を迎える。
• \(k\geq A_{i,j}\) であるようなある \(k\) 年目に、上下左右に隣接するいずれかの区画が海に沈み、新しく海に接するようになる。

言い換えると、各区画は海に接しない限り沈むことはなく、逆に海に接した瞬間に何年目に沈むかが直ちにわかります。具体的には、区画 \((i,j)\) が \(k\) 年目に初めて海に接したとき、

• \(A_{i,j}\leq k\) のとき、\(k\) 年目に沈む。
• \(k<A_{i,j}\leq Y\) のとき, \(A_{i,j}\) 年目に沈む。
• \(A_{i,j}\geq Y\) のとき、 \(Y\) 年目までに沈むことはない。

となります。

このことに注意して、\(Y\) 個の列(\(Y\)項からなる列ではないことに注意してください) \(Q_1\), \(Q_2\), \(\ldots\), \(Q_Y\) を用意し、\(Q_k\) の各項は現時点ですでに海に接している区画であって、 \(k\) 日目に沈む区画となるようなものを作り、更新していくことを考えます。

まず、島の外周, すなわち海と最初から接している区画について、便宜上 \(0\) 年目に初めて海に接したと考えることができます。 よって、外周の各 \((i,j)\) すなわち \(\{(i,j)|i=1 または i=H または j=1 または j=W\} \) は、（常に \(A_{i,j}\geq 0\) であることに注意すると）\(A_{i,j}\leq Y\) ならば \(A_{i,j}\) 年目に沈み、そうでなければ\(Y\) 年目までに沈むことはありません。なので外周の各 \((i,j)\) について、 \(A_{i,j}\leq Y\) ならば \(Q_{A_{i,j}}\) の末尾に \(A_{i,j}\) を追加します。

その後、\(k=1,2,\ldots,Y\) の順に次の操作を行います。

• \(Q_k\) の要素(区画) (\(Q_{k,1}, Q_{k,2},\ldots\)) を先頭から順に見ていく。
• \(Q_{k,l}\) と隣接する区画（高々 \(4\) つ）のうち、まだ海と接していない区画、すなわち\(Q_{k,l}\) が \(k\) 年目に海に沈むことで初めて海と接する区画について、その区画の標高 \(A_{i',j'}\)が \(k\) 以下ならば \(Q_k\) の末尾に、\((k+1)\) 以上 \(Y\) 以下ならば \(Q_{A_{i',j'}}\) の末尾にその区画を追加する。そうでなければ何もしない。

これらの操作を行うことによって、\(Y\) 年目までに沈む区画を列挙することができます。これらを最初の島の面積 \((H\times W)\) から順に引いていくことによって答えを求めることができます。

各区画は \(Q_1\), \(Q_2\), \(\ldots\), \(Q_Y\) のうち高々\(1\) つに \(1\) 回しか登場しません。また、列に含まれる各区画についての操作は、それと隣接する区画がすでに海と接しているか確認し、またその標高に応じて列に追加するだけであるため、計算量は全体で \(O(HW)\) となります。 本問題の制約下でこれは十分高速です。 よって、この問題を解くことができました。

c++ による実装例:

#include <bits/stdc++.h>
using namespace std;

#define MAX_H 1000
#define MAX_W 1000
#define MAX_Y 100000

int main(void){
	queue<int> q[MAX_Y+1];
	int a[MAX_H][MAX_W];
	bool inland[MAX_H][MAX_W];
	int h,w,n,ans,x,y,z;

	cin>>h>>w>>n;
	ans=h*w;
	for(int i=0;i<h;i++){
		for(int j=0;j<w;j++){
			cin>>a[i][j];
			inland[i][j]=true;
			if((i==0)||(i==h-1)||(j==0)||(j==w-1)){
				q[a[i][j]].push(w*i+j);
				inland[i][j]=false;
			}
		}
	}

	int dx[4]={0,0,-1,1};
	int dy[4]={1,-1,0,0};
	for(int i=1;i<=n;i++){
		while(!q[i].empty()){
			ans--;
			z=q[i].front();
			x=z/w,y=z%w;
			q[i].pop();
			for(int j=0;j<4;j++){
				if(((x+dx[j])>=0)&&((x+dx[j])<h)&&((y+dy[j])>=0)&&((y+dy[j])<w)){
					if(inland[x+dx[j]][y+dy[j]]){
						q[max(a[x+dx[j]][y+dy[j]],i)].push(w*(x+dx[j])+(y+dy[j]));
						inland[x+dx[j]][y+dy[j]]=false;
					}
				}
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}