题目描述

Farmer John的农夫上有很多小山丘，他想要在那里布置一些保镖（......）去保卫他的那些相当值钱的奶牛们。

他想知道如果在一座小山丘上布置一名保镖的话，他总共需要招聘多少名保镖。他现在手头有一个用数字矩阵来表示地形的地图。这个矩阵有N行（1＜N≤100）和M列（1＜M≤70）。矩阵中的每个元素都有一个值H_ij（0≤H_ij≤10000）来表示该地区的海拔高度。请你帮助他统计出地图上到底有多少个小山丘。

小山丘的定义是：若地图中一个元素所邻接的所有元素都不高于这个元素高度（或它邻接的是地图的边界）（即小于或等于），则该元素和其周围所有按照这样顺序排列的元素的集合称为一个小山丘。这里邻接的意义是：若一个元素与另一个横坐标纵坐标和它的横纵坐标相差不超过1，则称这两个元素邻接。（即某个非边界点跟它相邻的有8个点,上、下、左、右、左上、右上、左下、右下）

输入输出格式

输入格式：

第一行，两个由空格隔开的整数N和M；

第二行到第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

说明

样例说明：

地图上有三个小山丘：每个小山丘的山峰位置分别在左上角（高度为4），右上角（高度为1）和底部（高度为2）。

 

思路：入门题，队列宽搜。

//程序名:新的C++程序
//作者: 

#include<iostream>
#include<fstream>
#include<algorithm>
#include<queue>

using namespace std;
queue<int> a,b;
bool c[105][75];
int dx[8]={-1,-1,-1,0,0,1,1,1};
int dy[8]={-1,0,1,-1,1,-1,0,1};
int n,m,d[105][75],ans;
bool in(int x,int y)
{
    if(x>0&&x<=n&&y>0&&y<=m)return true;
    return false;
}
bool check()
{
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)if(c[i][j]==0)return true;
    return false;
}
void bfs(int x,int y)
{
    if(a.empty())return;
    //for(int i=1;i<=n;i++)
    //{for(int j=1;j<=m;j++)cout<<c[i][j]<<" ";cout<<endl;}cout<<endl;
    a.pop(),b.pop();
    for(int i=0;i<8;i++)
    {
        int nx=x+dx[i],ny=y+dy[i];
        if(in(nx,ny)&&d[nx][ny]<=d[x][y]&&!c[nx][ny])c[nx][ny]=1,a.push(nx),b.push(ny);
    }
    if(a.empty())return;
    bfs(a.front(),b.front());
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)cin>>d[i][j];
    while(check())
    {
        ans++;
        int MAX=-1,maxx=0,maxy=0;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)if(d[i][j]>MAX&&c[i][j]==0)MAX=d[i][j],maxx=i,maxy=j;
        a.push(maxx),b.push(maxy),c[maxx][maxy]=1;
        //cout<<"maxx:"<<maxx<<"maxy:"<<maxy<<endl;
        bfs(maxx,maxy);
    }
    cout<<ans;
    return 0;
}

View Code