rt

评测记录

#include<bits/stdc++.h>

using namespace std;

inline int read() {
	int ret=0,f=1;
	char c=getchar();
	for(; c<'0'||c>'9'; c=getchar()) if(c=='-') f=-f;
	for(; c>='0'&&c<='9'; c=getchar()) ret=ret*10+c-'0';
	return ret*f;
}
const int maxn=550;
int N,M;
bool vis[maxn][maxn];
int h[maxn][maxn];
int l[maxn][maxn],r[maxn][maxn];
int dx[5]={1,-1,0,0};
int dy[5]={0,0,-1,1};

inline void dfs(int x,int y){
	vis[x][y]=1;
	for(int i=0;i<4;i++){
		int ax=x+dx[i];
		int ay=y+dy[i];
		if(ax<1 || ax>N || ay<1 || ay>M) continue;
		if(h[ax][ay]>=h[x][y]) continue;
		if(!vis[ax][ay]) dfs(ax,ay);
		
		l[x][y]=min(l[x][y],l[ax][ay]);
		r[x][y]=max(r[x][y],r[ax][ay]);
	}
}

signed main(void) {
	
	memset(l,0x3f,sizeof(l));
	N=read();M=read();
	for(int i=1;i<=M;i++){
		l[N][i]=i;r[N][i]=i;
	}
	for(int i=1; i<=N; i++) {
		for(int j=1; j<=M; j++) {
//			cin>>h[i][j];
			h[i][j]=read();
		}
	}
	
	for(int i=1;i<=M;i++){
		if(!vis[1][i]){
			dfs(1,i);
		}
	}
	
	bool f=0;
	int cnt=0;
	for(int i=1;i<=M;i++){
		if(!vis[N][i]){
			f=1;
			cnt++;
		}
	}
	
	if(f){
		puts("0");
		printf("%d",cnt);
		return 0; 
	}
	
	int lef=1;
	while(lef<=M){
		int maxx=0;
		for(int i=1;i<=M;i++){
			if(l[1][i]<lef){
				maxx=max(maxx,r[1][i]);
			}
		}
		cnt++;
		lef=maxx+1;
	}
	
	puts("1");
	printf("%d",cnt);

	return 0;
}