1 条题解
-
0
#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
- 上传者