题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=3388
把高度相等的点看作一个点，然后答案就是max（入度为0，出度为0）
每次把一个没有访问过的点的相邻且相等的全都标记上，这些算作一个点，然后dfs的时候顺便记录下是否有更高的/更低的相邻
注意全部相等时，输出0
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
#include<bits/stdc++.h> #define MAXN 550 using namespace std; inline int rd(){ int x=0,y=1;char c=getchar(); while(!isdigit(c)){if(c=='-')y=-y;c=getchar();} while(isdigit(c))x=x*10+c-'0',c=getchar(); return x*y; } int n,m,ans1,ans2; int a[MAXN][MAXN],tot; bool vis[MAXN][MAXN]; int tox[4]={-1,0,1,0}; int toy[4]={0,1,0,-1}; void dfs(int x,int y,bool &f1,bool &f2){ vis[x][y]=1; for(int i=0; i<4; i++){ int xx=x+tox[i]; int yy=y+toy[i]; if(xx<1 || xx>n || yy<1 || yy>m)continue; if(a[xx][yy]>a[x][y])f1=1; if(a[xx][yy]<a[x][y])f2=1; if(!vis[xx][yy] && a[xx][yy]==a[x][y])dfs(xx,yy,f1,f2); } } int main(){ m=rd(),n=rd(); for(int i=1; i<=n; i++){ for(int j=1; j<=m; j++)a[i][j]=rd(); } int num=0; for(int i=1; i<=n; i++){ for(int j=1; j<=m; j++){ if(vis[i][j])continue; num++; bool f1=0,f2=0; dfs(i,j,f1,f2); if(!f1)ans1++; if(!f2)ans2++; } } if(num==1)puts("0"); else printf("%d\n",max(ans1,ans2)); return 0; } |
