专题一搜索 J - 山峰和山谷 Ridges and Valleys

2022/1/23 23:04:42

本文主要是介绍专题一搜索 J - 山峰和山谷 Ridges and Valleys,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

  1. 题目

    译自 POI 2007 Stage 2. Day 0「Ridges and Valleys」

    给定一个 n \times nn×n 的网格状地图,每个方格 (i,j)(i,j) 有一个高度 w_{ij}wij​。如果两个方格有公共顶点,则它们是相邻的。

    定义山峰和山谷如下:

    • 均由地图上的一个连通块组成;
    • 所有方格高度都相同;
    • 周围的方格(即不属于山峰或山谷但与山峰或山谷相邻的格子)高度均大于山谷的高度,或小于山峰的高度。

    求地图内山峰和山谷的数量。特别地,如果整个地图方格的高度均相同,则整个地图既是一个山谷,也是一个山峰。

    输入格式

    第一行一个整数 nn (2 \le n \le 10002≤n≤1000),表示地图的大小。

    接下来 nn 行每行 nn 个整数表示地图。第 ii 行有 nn 个整数 w_{i1}, w_{i2}, \ldots, w_{in} (0 \le w_{ij} \le 1\ 000\ 000\ 000)wi1​,wi2​,…,win​(0≤wij​≤1 000 000 000),表示地图第 ii 行格子的高度。

    输出格式

    输出一行两个整数,分别表示山峰和山谷的数量。

    样例 1
    Input Output
    5
    8 8 8 7 7
    7 7 8 8 7
    7 7 7 7 7
    7 8 8 7 8
    7 8 8 8 8
    2 1

    样例 2
    Input Output
    5
    5 7 8 3 1
    5 5 7 6 6
    6 6 6 2 8
    5 7 2 5 8
    7 1 0 1 7
    3 3

  2. 思路
    遍历地图每一个点,用广搜找连通块,找连通块过程中与周围的点进行比较,有比它高的则这个连通块不是山峰,有比它低的则这个连通块不是山谷。
    最开始我受到一些影响想着剪枝,结果剪出了错,我一开始的想法是bfs过程中如果已经搜到这个连通块不是山峰也不是山谷,就提前结束搜索,对于之后的点,如果它的邻居里和它值相同的点已经被搜过了,那么这个点和被搜过的点属于同一个连通块,直接跳过,后来发现不行,比如这个数据:
    3
    5 4 4
    5 6 5
    6 5 6
    用我错误剪枝思路结果是1 2,但是正确答案是1 1,去掉剪枝之后就过了。
    这告诉我,时间空间充足的情况下没事别乱剪枝,如果情况考虑不周全容易剪错。
  3. 代码
    #include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<algorithm>
    #include<queue>
    using namespace std;
    
    struct node{
    	int x,y;
    };
    struct node mov[8]={{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1}};
    
    int map[1005][1005];
    int vis[1005][1005];
    int h=0,l=0;
    int hight,low;
    int tx,ty,nx,ny,n;
    
    void bfs(int x,int y)
    {
    	queue<int> qx,qy;
    	qx.push(x);qy.push(y);
    	vis[x][y]=1;
    	while(!qx.empty()&&!qy.empty())
    	{
    		tx=qx.front(),qx.pop();
    		ty=qy.front(),qy.pop();
    		for(int i=0;i<=7;i++)
    		{
    			nx=tx+mov[i].x;
    			ny=ty+mov[i].y;
    			if(nx>=0&&nx<n&&ny>=0&&ny<n)
    			{
    				if(map[x][y]<map[nx][ny])
    				{
    					hight=0;
    				}
    				else if(map[x][y]>map[nx][ny])
    				{
    					low=0;
    				}
    				else if(map[x][y]==map[nx][ny]&&vis[nx][ny]==0)
    				{
    					qx.push(nx);
    					qy.push(ny);
    					vis[nx][ny]=1;
    				}
    			}
    			/*if(!hight && !low)
    			{
    				return;
    			}*/
    		}
    	}
    }
    
    /*int check(int x,int y)//检查这个点所在连通块是不是以前已经搜过了,搜了明显没必要再搜了
    {//如果搜过返回0,没搜返回1
    	for(int i=0;i<=7;i++)
    	{
    		nx=tx+mov[i].x;
    		ny=ty+mov[i].y;
    		if(nx>=0&&nx<n&&ny>=0&&ny<n)
    		{
    			if(map[x][y]==map[nx][ny]&&vis[nx][ny]==1)
    			{
    				vis[x][y]=1;
    				return 0;
    			}
    		}
    	}
    	return 1;
    }*/
    
    int main()
    {
    	scanf("%d",&n);
    	for(int i=0;i<n;i++){
    		for(int j=0;j<n;j++){
    			scanf("%d",&map[i][j]);
    		}
    	}
    	for(int i=0;i<n;i++){
    		for(int j=0;j<n;j++){
    			if(!vis[i][j]){
    				hight=1,low=1;
    				bfs(i,j);
    				h+=hight;
    				l+=low;
    			}
    		}
    	}
    	printf("%d %d\n",h,l);
    	return 0;
    }


这篇关于专题一搜索 J - 山峰和山谷 Ridges and Valleys的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程