编程练习-2022-06-03-Andy

题目描述

最近你刚买了一个方形小岛，就听说马上要全球变暖，冰川融化，你非常害怕。作为岛主，你想知道假设海平面上升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;
}