洪宇帆
(洪宇帆)
1
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 2005;
ll n,m,mx = -1,mn = 1e18,h[maxn][maxn],ans, col[maxn][maxn], lst[maxn];
bool ok[maxn][maxn];
void clear() {
for (int i = 1;i <= n;i ++)
for (int j = 1;j <= m;j ++)
col[i][j] ^= col[i][j];
}
void init() {
for (int i = 1;i <= n;i ++)
for (int j = 1;j <= m;j ++)
ok[i][j] ^= ok[i][j];
}
bool check(ll x) {
clear(); bool flag = true;
for (int i = 1;i <= n;i ++)
for (int j = 1;j <= m;j ++)
if (h[i][j] >= mx - x)
if (h[i][j] <= mn + x) col[i][j] = 3;
else col[i][j] = 1;
else if (h[i][j] <= mn + x) col[i][j] = 2;
else return false;
// check1
init(); ll l = 1, r = m;
for (int i = 1;i <= n;i ++) {
for (int j = 1;j <= r;j ++)
if (col[i][j] == 1 || col[i][j] == 3) ok[i][j] = true;
else { r = j - 1; break; }
if (col[i + 1][1] == 2)
break;
}
for (int i = n;i > 0;i --) {
for (int j = m;j >= l;j --) {
if (!ok[i][j] && col[i][j] != 1) ok[i][j] = 1;
else { l = j + 1; break; }
}
if (col[i - 1][m] == 1) break;
}
for (int i = 1;i <= n;i ++)
for (int j = 1;j <= m;j ++)
if (!ok[i][j]) flag = false;
if (flag) return true;
// check2
init(); flag = true, l = 1, r = m;
for (int i = n;i >= 1;i --) {
for (int j = 1;j <= r;j ++)
if (col[i][j] == 1 || col[i][j] == 3) ok[i][j] = true;
else { r = j - 1; break; }
if (col[i - 1][1] == 2)
break;
}
for (int i = 1;i <= n;i ++) {
for (int j = m;j >= l;j --) {
if (!ok[i][j] && col[i][j] != 1) ok[i][j] = 1;
else { l = j + 1; break; }
}
if (col[i + 1][m] == 1) break;
}
for (int i = 1;i <= n;i ++)
for (int j = 1;j <= m;j ++)
if (!ok[i][j]) flag = false;
if (flag) return true;
// check3
init(); flag = true, l = m, r = 1;
for (int i = 1;i <= n;i ++) {
for (int j = m;j >= r;j --)
if (col[i][j] == 1 || col[i][j] == 3) ok[i][j] = true;
else { r = j + 1; break; }
if (col[i + 1][1] == 2)
break;
}
for (int i = n;i > 0;i --) {
for (int j = 1;j <= l;j ++) {
if (!ok[i][j] && col[i][j] != 1) ok[i][j] = 1;
else { l = j - 1; break; }
}
if (col[i - 1][1] == 1) break;
}
for (int i = 1;i <= n;i ++)
for (int j = 1;j <= m;j ++)
if (!ok[i][j]) flag = false;
if (flag) return true;
// check4
init(); flag = true, l = m, r = 1;
for (int i = n;i >= 1;i --) {
for (int j = m;j >= r;j --)
if (col[i][j] == 1 || col[i][j] == 3) ok[i][j] = true;
else { r = j + 1; break; }
if (col[i - 1][m] == 2)
break;
}
for (int i = 1;i <= n;i ++) {
for (int j = 1;j <= l;j ++) {
if (!ok[i][j] && col[i][j] != 1) ok[i][j] = 1;
else { l = j - 1; break; }
}
if (col[i + 1][1] == 1) break;
}
for (int i = 1;i <= n;i ++)
for (int j = 1;j <= m;j ++)
if (!ok[i][j]) flag = false;
if (flag) return true;
return false;
}
int main() {
scanf("%lld%lld",&n,&m);
for (int i = 1;i <= n;i ++)
for (int j = 1;j <= m;j ++) {
scanf("%lld",&h[i][j]);
mx = max(mx,h[i][j]), mn = min(mn,h[i][j]);
}
ll l = 0,r = mx - mn,mid;
while (l <= r) {
mid = (l + r) >> 1;
if (check(mid)) ans = mid, r = mid - 1;
else l = mid + 1;
}
printf("%lld",ans);
return 0;
}
/*
4 4
1 12 6 11
11 10 2 14
10 1 9 20
4 17 19 10
*/
/*
8 6
23 23 10 11 16 21
15 26 19 28 19 20
25 26 28 16 15 11
11 8 19 11 15 24
14 19 15 14 24 11
10 8 11 7 6 14
23 5 19 23 17 17
18 11 21 14 20 16
*/
4 个赞