题目描述
最近你刚买了一个方形小岛，就听说马上要全球变暖，冰川融化，你非常害怕。作为岛主，你想知道假设海平面上升H米，你的小岛还有剩多少面积没被淹没。对于海水能触及的地方，初始海拔大于H才不会被淹。方形小岛由n*n块面积为1的小方块组成，第i行第j列的方块海拔h[i][j]米。海水在方块间流动可以有8个方向。
输入输出格式
输入格式
输入第一行为正整数n和整数H，之后为n行n列个整数。n<=200，-100<=H,h[i][j]<=100。
输出格式
输出一个整数代表剩余面积。
标签
图论 八联通 DFS
AC代码
#include <bits/stdc++.h>
using namespace std;
int dx[9]={0,1,1,1,0,0,-1,-1,-1},dy[9]={0,1,0,-1,1,-1,1,0,-1},x,y,e,r,n,ans;
int h,a[200][200];
char vst[200][200];
void print(){
cout<<"=============="<<endl;
for(int i=0;i<=n+1;i++,cout<<endl){
for(int j=0;j<=n+1;j++){
cout<<vst[i][j]<<' ';
}
}
cin.get();
}
void dfs(int d,int f){
if(a[d][f]>h)return;
if(vst[d][f]=='@')return;
vst[d][f]='@';
for(int k=1;k<=8;k++){
int nd=d+dx[k],nf=f+dy[k];
if(nd>=0&&nd<=n+1&&nf>=0&&nf<=n+1&&vst[nd][nf]=='-'){
ans++;
//print();
dfs(nd,nf);
}
}
}
int main()
{
// freopen("volcano.in","r",stdin);
//freopen("volcano.out","w",stdout);
cin>>n>>h;
for(int i=0;i<=n+1;i++)a[i][0]=h,vst[i][0]='@';
for(int i=0;i<=n+1;i++)a[0][i]=h,vst[0][i]='@';
for(int i=0;i<=n+1;i++)a[i][n+1]=h,vst[i][n+1]='@';
for(int i=0;i<=n+1;i++)a[n+1][i]=h,vst[n+1][i]='@';
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cin>>a[i][j];
for(int i=0;i<=n+1;i++){
for(int j=0;j<=n+1;j++){
if(a[i][j]>h)vst[i][j]='+';
else vst[i][j]='-';
}
}
dfs(0,0);
// print();
ans=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(vst[i][j]!='@')ans++;
}
}
cout<<ans;
return 0;
}
