abc 363E
作者:
Air1222
,
2024-10-09 22:16:36
,
所有人可见
,
阅读 4
//题目回忆:给一张海拔图,每年海拔上升1m,求k年,每年还剩多少岛
//自己思路:想套海水填充模型,无果
//暴力思路:每年跑一边海水填充(TLE)
//正确思路,利用小根堆,每一次找一个最小值,如果小于当前年,则用它开始遍历,并将当前点弹出,并将当前点的四周压入(四周变成海岸)
//注意continue,作用不仅在for循环内,而在整个函数
#include <iostream>
#include <queue>
#define x first
#define y second
using namespace std;
typedef pair<int,pair<int,int>>PIII;
const int N = 1010;
int g[N][N];
bool st[N][N];
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
int n,m,k;
int main()
{
priority_queue<PIII, vector<PIII>, greater<PIII>>q;
cin>>n>>m>>k;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
cin>>g[i][j];
if(i==1||i==n||j==1||j==m)
{
q.push({g[i][j],{i,j}});
st[i][j]=true;
}
}
int sum=n*m;
for(int i=1;i<=k;i++)
{
//cout<<q.top().x<<endl;
while(q.top().x<=i&&!q.empty())
{
auto t=q.top();
//cout<<i<<" "<<t.y.x<<" "<<t.y.y<<endl;
q.pop();
sum--;
for(int i=0;i<4;i++)
{
int a=t.y.x+dx[i],b=t.y.y+dy[i];
if(a<1||a>n||b<1||b>m) continue;
if(st[a][b]) continue;
st[a][b]=true;
q.push({g[a][b],{a,b}});
}
}
cout<<sum<<endl;
}
}