二分加广搜
#include <bits/stdc++.h>
using namespace std;
int n, m, l, r, p[1001][1001], vis[1001][1001];
int dx[6] = {0, 1, -1, 0, 0};
int dy[6] = {0, 0, 0, 1, -1};
int qx[100100], qy[1001001];
bool check(int d)
{
memset(vis, 0, sizeof(vis));
int front = 0, tail = 0;
for (int i = 1; i <= m; i++)
qx[++tail] = i, qy[tail] = 1;
int tot = 0;
while (front <= tail)
{
int nx = qx[front], ny = qy[front++];
if (ny == n)
tot++;
for (int i = 1; i <= 4; i++)
{
int ax = nx + dx[i];
int ay = ny + dy[i];
if (p[ay][ax] <= d && !vis[ay][ax] && (ax <= m && ax >= 1 && ay <= n && ay >= 1))
qx[++tail] = ax, qy[tail] = ay, vis[ay][ax] = 1;
}
}
if (tot == m) return 1;
return 0;
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
scanf("%d", &p[i][j]), r = max(r, p[i][j]);
int mid = 0, ans = 0;
while (l <= r)
{
mid = (l + r) >> 1;
if (check(mid))
ans = mid, r = mid - 1;
else l = mid + 1;
}
printf("%d", ans);
return 0;
}