1 条题解

  • 0
    @ 2025-2-25 15:56:17
    #include <bits/stdc++.h>
    using namespace std;
    const int maxn=1010;
    const int INF=0x3fffffff;
    typedef long long LL;
    typedef unsigned long long ull;
    //广搜的剪枝 ,每个点进行广搜,每搜完一个点,把与它相连接的点标记,不重复的搜。
    //特别注意,如果整个地图方格的高度均相同,则整个地图既是一个山谷,也是一个山峰。
    int mp[maxn][maxn];
    int n,high,low,cnt,vis[maxn][maxn];
    int dis[10][2]={0,1,0,-1,1,0,-1,0,1,-1,-1,-1,-1,1,1,1}; //md这个写错了!!
    struct node{
    	int x,y;
    	//node(int xx,int yy) x(xx),y(yy){};
    };
    void BFS(int x1,int y1){
    	bool flag1=0,flag2=0;
    	int cnt=1;
    	vis[x1][y1]=1;
    	queue<node> q;
    	node now,pre;
    	pre.x=x1;
    	pre.y=y1;
    	q.push(pre);
    	while(!q.empty()){
    		now=q.front();
    		q.pop();
    		for(int i=0;i<8;i++){
    			pre.x=now.x+dis[i][0];
    			pre.y=now.y+dis[i][1];
    			
    			if(pre.x>n||pre.y>n||pre.x<=0||pre.y<=0||(vis[pre.x][pre.y]&&mp[pre.x][pre.y]==mp[now.x][now.y]))
    //标记已走过的坐标,且改坐标对应的值与之前的值相同
    				continue;
    			else if(mp[pre.x][pre.y]==mp[now.x][now.y]){
    				q.push(pre);
    				vis[pre.x][pre.y]=true;
    				cnt++;
    				//cout<<cnt<<endl;
    			}
    			else{
    				if(mp[now.x][now.y]>mp[pre.x][pre.y])
    					flag1=true;
    				else
    					flag2=true;
    			}
    		}
    	}
    	if(flag1&&flag2) return;
    	else if(flag1) high++;
    	else if(flag2) low++;
    	if(cnt==n*n) {
    		low++;high++;
    	}
    	return;
    }
    int main(){
    	scanf("%d",&n);
    	low=0;high=0;
    	for(int i=1;i<=n;i++){
    		for(int j=1;j<=n;j++){
    			cin>>mp[i][j];
    		}
    	}
    	memset(vis,0,sizeof(vis));
    	for(int i=1;i<=n;i++){
    		for(int j=1;j<=n;j++){
    			if(!vis[i][j]) {
    				//  cout<<"heihei "<<i<<j<<endl;
    				BFS(i,j);
    				
    			}
    		}
    	}
    	printf("%d %d",high,low);
    	return 0;
    }
    
    • 1

    信息

    ID
    910
    时间
    1000ms
    内存
    512MiB
    难度
    10
    标签
    (无)
    递交数
    1
    已通过
    0
    上传者