#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pb push_back
#define endl "\n"
#define fr first
#define sc second
#define sz size()
#define ins insert
#define bc back()
#define str string
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
void fre(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
void start(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
const ll inf=1e18+7;
const ll mod=1e9;
const ll N=2e3+7;
const ld eps=1e-9;
ll xx[4]={1,-1,0,0},yy[4]={0,0,1,-1};
bool vis[N][N],good[N][N],need[N][N];
ll a[N][N],mx=0,mn=inf;
ll n,m;
ll i,j;
ll bfs(ll x,ll y){
ll c=0;
queue<pair<ll,ll>> q;
q.push({x,y});
vis[x][y]=true;
while(q.sz){
ll x=q.front().fr,y=q.front().sc;
if(need[x][y])c++;
q.pop();
for(i=0;i<4;i++){
if(good[x+xx[i]][y+yy[i]] && !vis[x+xx[i]][y+yy[i]]){
q.push({x+xx[i],y+yy[i]});
vis[x+xx[i]][y+yy[i]]=true;
}
}
}
return c;
}
bool check(ll mid){
ll x,y,c=0;
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
if(a[i][j]<mx-mid){
x=i;
y=j;
c++;
need[i][j]=true;
}else need[i][j]=false;
if(a[i][j]<=mn+mid)good[i][j]=true;
else good[i][j]=false;
vis[i][j]=false;
}
}
if(c!=bfs(x,y))return false;
c=0;
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
if(a[i][j]>mn+mid){
x=i;
y=j;
c++;
need[i][j]=true;
}else need[i][j]=false;
if(a[i][j]>=mx-mid) good[i][j]=true;
else good[i][j]=false;
vis[i][j]=false;
}
}
if(c!=bfs(x,y))return false;
vector<ll> v;
for(i=1;i<=n;i++){
x=a[i][1];
if(x>mn+mid)v.pb(1);
else if(x<mx-mid)v.pb(2);
else v.pb(0);
}
for(i=2;i<=m;i++){
x=a[n][i];
if(x>mn+mid)v.pb(1);
else if(x<=mx-mid)v.pb(2);
else v.pb(0);
}
for(i=n-1;i>0;i--){
x=a[i][m];
if(x>mn+mid)v.pb(1);
else if(x<=mx-mid)v.pb(2);
else v.pb(0);
}
for(i=m-1;i>0;i--){
x=a[1][i];
if(x>mn+mid)v.pb(1);
else if(x<=mx-mid)v.pb(2);
else v.pb(0);
}
c=0;
x=0;
for(i=0;i<(ll)v.sz-1;i++){
if(i<v.sz-2 && v[i]==1 && x==2) c++;
if(v[i])x=v[i];
}
if(x>0){
for(i=0;i<(ll)v.sz-1;i++){
if(v[i]){
if(v[i]!=x)c++;
else break;
}
}
}
if(c>1)return false;
return true;
}
void solve(){
cin>>n>>m;
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
cin>>a[i][j];
mx=max(mx,a[i][j]);
mn=min(mn,a[i][j]);
}
}
if(mn==mx){
cout<<0<<endl;
return;
}
ll l=0,r=mx-mn;
while(r-l>1){
ll mid=(l+r)/2;
if(check(mid))r=mid;
else l=mid;
}
cout<<r<<endl;
}
signed main(){
start();
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
ll t=1;
//cin>>t;
while(t--) solve();
}
/*
*/
Compilation message
joioi.cpp: In function 'bool check(long long int)':
joioi.cpp:111:7: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
111 | if(i<v.sz-2 && v[i]==1 && x==2) c++;
| ~^~~~~~~
joioi.cpp: In function 'void fre(std::string)':
joioi.cpp:19:27: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
19 | void fre(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
joioi.cpp:19:64: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
19 | void fre(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
joioi.cpp: In function 'bool check(long long int)':
joioi.cpp:67:11: warning: 'y' may be used uninitialized in this function [-Wmaybe-uninitialized]
67 | if(c!=bfs(x,y))return false;
| ~~~^~~~~
joioi.cpp:67:11: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
6492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
6492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
6492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
