思路：
Tarjan缩点+一些特判//By SiriusRen#include#include #include #include #include using namespace std;stack stk;int n,m,map[666][666],xx[]={ 1,-1,0,0},yy[]={ 0,0,1,-1};int v[1001000],next[1001000],first[1001000],tot=0,ans1=0,ans2=0;int low[1001000],dfn[1001000],cnt=0,vis[1001000],t=0,p[1001000],out[1001000],in[1001000];bool check(int sx,int sy,int x,int y){ return map[sx][sy]>=map[x][y]&&x>=1&&x<=n&&y>=1&&y<=m;}void add(int x,int y){v[tot]=y,next[tot]=first[x];first[x]=tot++;}void tarjan(int x){ dfn[x]=low[x]=++cnt; vis[x]=1;stk.push(x); for(int i=first[x];~i;i=next[i]) { if(!dfn[v[i]])tarjan(v[i]),low[x]=min(low[x],low[v[i]]); else if(vis[v[i]])low[x]=min(low[x],dfn[v[i]]); } if(low[x]==dfn[x]) { t++; int temp; do { temp=stk.top();stk.pop(); vis[temp]=0; p[temp]=t; }while(temp!=x); }}int main(){ memset(first,-1,sizeof(first)); scanf("%d%d",&m,&n); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { scanf("%d",&map[i][j]); } } for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { for(int k=0;k<=3;k++) { if(check(i,j,i+xx[k],j+yy[k])) { add(i*m+j,(i+xx[k])*m+j+yy[k]); } } } } for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { if(!dfn[i*m+j]) { tarjan(i*m+j); } } } for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { for(int k=0;k<=3;k++) { if(check(i,j,i+xx[k],j+yy[k])&&p[i*m+j]!=p[(i+xx[k])*m+j+yy[k]]) { out[p[i*m+j]]++;in[p[(i+xx[k])*m+j+yy[k]]]++; } } } } for(int i=1;i<=t;i++) { if(!out[i])ans1++; if(!in[i])ans2++; } if(t>1)printf("%d",max(ans1,ans2)); else putchar('0');}
