WZK旅游

发布于 2019-04-04  8 次阅读


题目描述

【题目背景】
WZK喜欢旅游,因此,WZK去过很多很多美丽的地方,西双版纳,大理,九寨沟,黄龙,张家界,天涯海角„„
WZK发现,旅游景点普遍都有山水,山水萦绕,或朦胧悠远,或壮丽秀美,山水交织,总能有一翻绝伦的景致的!
不过WZK也发现,在这个虚假宣传泛滥的年代„„很多地方并不是像宣传画上说的那么漂亮的——比如——我可以把常州的横山说的像雁荡山那么漂亮——不过你到了之后才发现不过一座小山(当然,说小土坡WZK也不反对)——哪里能和祖国东南丘陵的大好山川相媲美呢?
好在,WZK知道如何利用Google Map对景点进行测试!Google Map是Google Web2.0的经典应用,有的时候,你甚至可以在Google Map上找到你的家的位置  。不过——不管怎么精确的卫星——毕竟没军用的那么强大,精确度总是有缺陷的——但至少,告诉你一个小的矩形区域的高度还是没有问题的——如果把目标区域划分成N*M的小区域,那么你可以知道每个小区域的高度。
不过„„由于景点的区域实在太大了,WZK对于google Map提供的硕大的地图感到很头疼,你能帮他么?
他需要你找出地图中所有的山峰了,湖泊。
WZK对湖泊和山峰的定义是这样的:
众所周知,水往低处流,WZK心中的湖泊还是一平如镜的,因此湖泊必然是一块连通的并且高度都相同区域,并且,这个区域的高度比其周围部分的高度都要低。
山峰的定义也是类似,WZK认为山峰一定是最高的,因此山峰必然是是一块连通的并且高度都相同区域,并且,这个区域的高度比其周围部分的高度都要高。
这里的周围指的是有边相邻的格子(对角的格子不算)。
WZK希望知道湖泊和山峰的个数,以便于对这个景点的优美程度进行估价。
显然一块大平地不会成为景点——因此不会出现每个小区域高度都相同的情况的。
好了现在轮到你了。
【问题描述】
给出N*M格的每格的高度信息,求出湖泊个数和山峰个数。

输入

第一行两个整数N,M。
接着N行,每行有M个数字,表示高度信息,之间用一个空格隔开。

输出

输出一行两个整数,分别表示湖泊个数和山峰个数,之间用一个空格隔开。

思路

广搜遍历每一个相同的数的点,判断上下左右四个方向的状态记录下来,如果只有大于或小于的话就累加

const
  dx:array[1..4] of integer=(1,0,-1,0);
  dy:array[1..4] of integer=(0,1,0,-1);
var
  a:array[-10..2001,-10..2001] of longint;
  f:array[-10..2001,-10..2001] of boolean;
  sx,sy:array[0..1000000] of longint;
  i,j,k,n,m,s,x,y,u,d,l,r:longint;
  up,down:boolean;

procedure bfs;
var
  head,tail,i,j,k:longint;
begin
  head:=0; tail:=1;sx[1]:=l; sy[1]:=r;
  while (head=1) and (sx[head]+dx[i]<=n) and (sy[head]+dy[i]>=1) and (sy[head]+dy[i]<=m) then
      begin
        if a[sx[head]+dx[i],sy[head]+dy[i]]=1) and (sx[head]+dx[i]<=n) and (sy[head]+dy[i]>=1) and (sy[head]+dy[i]<=m) and (not f[sx[head]+dx[i],sy[head]+dy[i]]) and (a[sx[head]+dx[i],sy[head]+dy[i]]=a[sx[head],sy[head]]) then
          begin
            inc(tail);
            sx[tail]:=sx[head]+dx[i];
            sy[tail]:=sy[head]+dy[i];
            f[sx[tail],sy[tail]]:=true;
          end
    end;

end;

begin
  assign(input,'seek.in'); reset(input);
  assign(output,'seek.out'); rewrite(output);
  readln(n,m);
  for i:=1 to n do
    begin
      for j:=1 to m do
        read(a[i,j]);
      readln;
    end;

  for i:=1 to n do
    for j:=1 to m do
      begin
        up:=false;
        down:=false;
    if not f[i,j] then begin f[i,j]:=true; l:=i; r:=j; bfs; end;
    if (up) and (not down) then inc(u)
      else if (down) and (not up) then inc(d);
      end;
  writeln(u,' ',d);
end.
]]>