emm骚操作
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #define rint register int #define max(a,b) (a>b?a:b) #define min(a,b) (a<b?a:b) #define swap(a,b) (a^=b,b^=a,a^=b) template <class T>inline void read(T &X) { X=0;int W=0;char ch=0; while(!isdigit(ch))W|=ch=='-',ch=getchar(); while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar(); X=W?-X:X;return; } int n,m,a[2010][2010],ma=-1,mi=99999999,ans=999999999; void turn() { for(rint i=1;i<=n;++i) for(rint j=1;j<=m/2;++j) swap(a[i][j],a[i][m-j+1]); } void down() { for(rint i=1;i<=n/2;++i) for(rint j=1;j<=m;++j) swap(a[i][j],a[n-i+1][j]); } int check(int x) { int to=m+1; for(rint i=1;i<=n;++i) { int t=0; for(rint j=1;j<=min(to,m);++j) if(ma-a[i][j]<=x)t=max(t,j); else break; to=t; for(rint j=t+1;j<=m;++j) if(a[i][j]-mi>x)return 0; } return 1; } int sep() { int l=1,r=ma-mi+1; while(l<=r) { int mid=l+r>>1; if(check(mid))r=mid-1; else l=mid+1; } return l; } int main() { freopen("separate.in","r",stdin); freopen("separate.out","w",stdout); read(n),read(m); for(rint i=1;i<=n;++i) for(rint j=1;j<=m;++j) { read(a[i][j]); ma=max(ma,a[i][j]); mi=min(mi,a[i][j]); } ans=min(ans,sep()); turn(); ans=min(ans,sep()); down(); ans=min(ans,sep()); turn(); ans=min(ans,sep()); printf("%d ",ans); return 0; }