问题4501--上午班题3

4501: 上午班题3

时间限制: 1 Sec  内存限制: 512 MB
提交: 0  解决: 0
[提交] [状态] [讨论版] [命题人:]

题目描述

灰太狼领导着狼群进攻羊村,羊村前有一座山峦,喜羊羊决定在每一个山顶上布置慢羊羊最新发明的寻狼导弹,为了争取时间,喜羊羊要用最短的时间找出所有山顶,聪明的喜羊羊想寻求你的帮助,从而赶走灰太狼。 你现在有一张软绵绵遗留下来的神秘地图,数字代表此地的高度,用一矩阵表示;矩阵有N (1 < N <= 700) 行 M (1 < M <= 700) 列。 矩阵中的每个数表示一个海拔高度H_ij (0 <= H_ij <= 10,000)。现在请你编写一道程序帮助喜羊羊确定地图上有几个山顶。 一个山顶是指这个矩阵元素的值与一个或多个相邻的矩阵元素的值相同或者相邻元素的值比这个元素值小。两个不同元素的相邻是指它们的X、Y坐标值相差均不超过1。 要注意的是:按照先行后列的顺序确定山顶,当一个山顶确定后,相邻的位置都同属于这个山顶,不会再出现第二个山顶,相邻位置作为这个山顶的一部分,如果它的高度不小于它的相邻元素,则它的相邻元素也同属于这一个山顶,以此类推,直到相邻的元素大于本身,才不属于。

输入

第一行:两个用空格隔开的整数: N 和 M 第 2..N+1行: 第 i+1 行用M个用空格隔开的整数H_ij表示矩阵的第i行第j列的高度

输出

一个整数表示小山顶的数目

样例输入

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

样例说明:上图中有3个山顶的位置(按行列的顺序出现)
第1行第1列4
第1行第7列1
第7行第3列2

来源/分类

 

[提交] [状态]