思路

仔细观察可以发现，其实每次海水上涨只会淹没沿岸的城市及其周边城市（废话），所以每次访问只需访问所有沿岸城市即可，总时间复杂度为$O(T(N+M))$（这规范吗？）。

AC代码

#include<bits/stdc++.h>
using namespace std;
const int N=1100;
int dx[4]={1,0,-1,0};
int dy[4]={0,-1,0,1};
struct node{int v,x,y;};//存储一个城市，三个参数分别表示海拔，坐标
bool operator <(node n1,node n2){return n1.v>n2.v;}//重载运算符 
int h,w,y,a[N][N],ans;
bool vis[N][N];//是否访问过？ 
priority_queue<node>Q;//存储沿岸城市 
int main()
{
	scanf("%d%d%d",&h,&w,&y);
	for(int i=1;i<=h;i++)for(int j=1;j<=w;j++)
	{
		scanf("%d",&a[i][j]);
		if(i==1||i==h||j==1||j==w)//先把沿岸城市存储 
		{
			vis[i][j]=1;
			Q.push({a[i][j],i,j});
		}
	}
	ans=h*w;//一开始都没被淹 
	for(int i=1;i<=y;i++)
	{
		while(!Q.empty()&&Q.top().v<=i)//bfs
		//第二个条件是为了防止访问到比当前海拔还高的城市，毕竟都
		//不可能被淹 
		{
			int x=Q.top().x,y=Q.top().y,v=Q.top().v;Q.pop();
			ans--;//坏了，被淹了 
			for(int j=0;j<4;j++)//枚举周边城市 
			{
				int xx=x+dx[j],yy=y+dy[j];
				if(xx>=1&&xx<=h&&yy>=1&&yy<=w&&!vis[xx][yy])
				{
					vis[xx][yy]=1;
					Q.push({a[xx][yy],xx,yy});
				}
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}

关于时间复杂度

乍一看题解我还以为$O(N^2)$，仔细一想才发现是$O(T(N+M))$，不过还有一种可能，每一个节点最多访问一次，加上$priotity$_$queue$的维护，总时间复杂度$O(N^2logN)$（也许吧）

以上很多内容纯属瞎猜，求打捞提建议。