守衛農場題解

題面

【問題描述】

農夫 John 的農場里有很多小山丘，他想要在那裡佈置一些保鏢去保衛他的那些相當值錢的奶牛們。 他想知道如果在一座小山丘上佈置一名保鏢的話，他總共需要招聘多少名保鏢。他現在有一個用數 字矩陣來表示地形的地圖。這個矩陣有 N 行和 M 列。矩陣中的每個元素都有一個值 H_ij 來表示該地區 的海拔高度。請你幫助他統計出地圖上到底有多少個小山丘。 小山丘的定義是：若地圖中一個元素所鄰接的所有元素都比這個元素高度要小或者相等（或它鄰接 的是地圖的邊界）， 則該元素和其周圍所有按照這樣順序排列的元素的集合稱為一個小山丘（本題某個 非邊界點跟它相鄰的有 8 個點：上、下、左、右、左上、右上、左下、右下）。

【輸入格式】

第 1 行：兩個由空格隔開的整數 N 和 M；

第 2 行到第 N+1 行：第 I+1 行描述了地圖上的第 I 行，有 M 個由空格隔開的整數： H_ij。

【輸出格式】

一個整數，表示小山丘的個數。

【輸入樣例】

 8 7 4 3 2 2 1 0 1 3 3 3 2 1 0 1 2 2 2 2 1 0 0 2 1 1 1 1 0 0 1 1 0 0 0 1 0 0 0 0 1 1 1 0 0 1 2 2 1 1 0 0 1 1 1 2 1 0

【輸出樣例】

3

【樣例解釋】

樣例中，小山丘的中心點分別為（1， 1），（7， 3），（1， 7）。//多了這個

【數據規模】

  對於 70%的數據： 1<N≤100； 1<M≤100；

對於 100%的數據： 1<N≤700； 1<M≤700； O≤H_ij≤10,000；

題解：

#include<bits/stdc++.h>
using namespace std;
int dx[]={-1,-1,-1, 0, 0, 1, 1, 1};//從八個方向去搜索即可（上下左右等） 
int dy[]={-1, 0, 1,-1, 1,-1, 0, 1};
//也可以 int dx[8]={-1,-1,-1, 0, 0, 1, 1, 1};
//int dy[8]={-1, 0, 1,-1, 1,-1, 0, 1}; 8個方向8個元素即可搜索 
int n,m,flag;
int v[710][710],a[710][710];
int check(int i, int j)
{
    if(i>=0&&i<n&&j>=0&&j<m)
return 1;
    return 0;
}
/*
bool check(int i,int j)
{
    if(i>=0&&i<n&&j>=0&&j<m)
    return true;
    return false;
} //用bool的寫法 true==1，false==0； 
*/ 
void dfs(int i,int j)//廣搜 
{
    int x,y;
    for(int k=0;k!=8;++k)
    {
       x=i+dx[k];
       y=j+dy[k];
       if (check(x,y))
       {
           if (a[x][y]>a[i][j])
           flag = 0;
if (!v[x][y]&&a[x][y]==a[i][j])
           {
               v[x][y] = 1;
               dfs(x,y);
           }
       }
    }
}
/*
inline int read(){
    int ret=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9') {if (ch=='-') f=-f;ch=getchar();}
    while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}
*/ 
int main()
{
    //freopen("guard.in","r",stdin); //文件輸出流！！ 
 //freopen("guard.out","w",stdout); 
    scanf("%d%d",&n,&m);//讀入可用讀優inline 優化加快讀入
    /*n=read();m=read();
    */
    for(int i=0;i!=n;++i)
        for (int j=0;j!=m;++j)
        {
            scanf("%d",&a[i][j]);
            //a[i][j]=read();
            v[i][j]=0;//初始化為0 
        }
    int ans=0;//統計小丘個數初始化為0 
    for(int i=0;i!=n;++i)//先加再做下一步 
        for(int j=0;j!=m;++j)
        if(a[i][j]&&!v[i][j])
        {
            flag=1;//為真，相加即可 
            dfs(i,j);//廣度優先搜索dfs 
            ans+=flag;
        }
    cout<<ans<<endl;//輸出 
return 0;
}