#include <iostream> #include <vector> #include <algorithm> #include <tuple> using namespace std; const int MAX_BOARD_LENGTH = 2000; const int MAX_VAL = 1e9; int height, width; int max_val=-1, min_val=MAX_VAL+7; int board[MAX_BOARD_LENGTH+7][MAX_BOARD_LENGTH+7]; int tmp[MAX_BOARD_LENGTH+7][MAX_BOARD_LENGTH+7]; void boardRotate90(){ for (int i = 1; i <= height; ++i) for (int j = 1; j <= width; ++j) tmp[width-j+1][i] = board[i][j]; swap(height, width); for (int i = 1; i <= height; ++i) for (int j = 1; j <= width; ++j) board[i][j] = tmp[i][j]; } void boardFlipHorizontal(){ for (int i = 1; i <= height; ++i) for (int j = 1; j <= width; ++j) tmp[i][width-j+1] = board[i][j]; for (int i = 1; i <= height; ++i) for (int j = 1; j <= width; ++j) board[i][j] = tmp[i][j]; } bool isAchievable(int k){ if (max_val - min_val <= k) return true; int curr_max=-1, curr_min=MAX_VAL+7; int max_height = 0; for (int j = 1; j <= width; ++j){ int i = height; while(i > max_height && board[i][j] <= min_val + k) i--; max_height = i; while(i > 0){ curr_max = max(curr_max, board[i][j]); curr_min = min(curr_min, board[i][j]); --i; } } return (curr_max - curr_min <= k); } int getRes(){ int low=0, high=max_val-min_val; while(low < high){ int mid = (low+high)/2; if (isAchievable(mid)) high = mid; else low = mid+1; } return high; } void showBoard(){ for (int i = 1; i <= height; ++i){ for (int j = 1; j <= width; ++j) cout << board[i][j] << ' '; cout << '\n'; } cout << '\n'; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> height >> width; for (int i = 1; i <= height; ++i) for (int j = 1; j <= width; ++j){ cin >> board[i][j]; max_val = max(max_val, board[i][j]); min_val = min(min_val, board[i][j]); } int res = getRes(); //showBoard(); boardRotate90(); res = min(res, getRes()); //showBoard(); boardRotate90(); res = min(res, getRes()); //showBoard(); boardRotate90(); res = min(res, getRes()); //showBoard(); cout << res << '\n'; return 0; }