#include <bits/stdc++.h>
#define loop(i,a,b) for(int i = (a); i < (b); i ++)
#define pb push_back
#define BAE(x) x.begin(), x.end()
#define unisort(x) sort(BAE(x)); x.resize(unique(BAE(x)) - x.begin())
using namespace std;
typedef long long ll;
const int mxn = 2005;
const int mxA = 4050000;
int n, m, area, ans;
int a[mxn][mxn];
int col[mxA];
vector<int> E[mxA];
inline pos(int x, int y){
return x * m + y;
}
bool dfs(int v){
// cout << "v = " << v << '\n';
for(auto &i:E[v]){
if(col[i] == 0){
col[i] = (col[v] == 1) ? 2 : 1;
if(!dfs(i)){
return false;
}
}
else if(col[i] == col[v]){
return false;
}
}
return true;
}
inline bool check(int val){
loop(i,0,area){
E[i].clear();
col[i] = 0;
}
loop(i,0,n){
loop(j,0,m){
loop(k,i,n){
loop(l,j,m){
if(abs(a[i][j] - a[k][l]) > val){
// cout << "(" << i << ", " << j << ") (" << k << ", " << l << ")\n";
E[pos(i, j)].pb(pos(k, l));
E[pos(k, l)].pb(pos(i, j));
}
}
}
}
}
loop(i,0,area){
if(col[i] == 0 && (!E[i].empty())){
// cout << "i = " << i << '\n';
col[i] = 1; // 1:white, 2:black
if(!dfs(i)) return false;
}
}
// loop(i,0,n){
// loop(j,0,m) cout << col[pos(i, j)] << ' ';
// cout << endl;
// }
loop(i,0,n){
int flip = -1, tmp = 0;
loop(j,0,m){
if(col[pos(i, j)] == 0) continue;
if(flip == -1){
tmp = col[pos(i, j)];
flip = 0;
}
else if(tmp != col[pos(i, j)]){
tmp = col[pos(i, j)];
flip += 1;
}
}
if(flip >= 2) return false;
}
loop(j,0,m){
int flip = -1, tmp = 0;
loop(i,0,n){
if(col[pos(i, j)] == 0) continue;
if(flip == -1){
tmp = col[pos(i, j)];
flip = 0;
}
else if(tmp != col[pos(i, j)]){
tmp = col[pos(i, j)];
flip += 1;
}
}
if(flip >= 2) return false;
}
return true;
}
int main(){
ios::sync_with_stdio(false); cin.tie(0);
// freopen("in.txt", "r", stdin);
cin >> n >> m;
area = n * m;
loop(i,0,n){
loop(j,0,m){
cin >> a[i][j];
}
}
vector<int> v;
loop(i,0,n){
loop(j,0,m){
loop(k,i,n){
loop(l,j,m){
v.pb(abs(a[i][j] - a[k][l]));
ans = max(ans, abs(a[i][j] - a[k][l]));
}
}
}
}
unisort(v);
// for(auto &i:v){
// cout << i << ' ';
// } cout << endl;
int l = 0, r = v.size() - 1, mid;
while(l < r){
mid = (l + r) >> 1;
if(check(v[mid])){
ans = v[mid];
r = mid;
}
else{
l = mid + 1;
}
}
cout << ans << '\n';
}
Compilation message
joioi.cpp:17:8: error: ISO C++ forbids declaration of 'pos' with no type [-fpermissive]
17 | inline pos(int x, int y){
| ^~~
