61 lines
1.8 KiB
C++
61 lines
1.8 KiB
C++
#include <iostream>
|
|
#include <queue>
|
|
#include <tuple>
|
|
|
|
using namespace std;
|
|
|
|
using pos = tuple<long, long>;
|
|
using node = tuple<long, long>;
|
|
|
|
const auto MAX = static_cast<long>(1e10);
|
|
|
|
int main()
|
|
{
|
|
long m, n, x; cin >> m >> n;
|
|
vector<vector<node>> vault(m, vector<node>(n));
|
|
vector<vector<bool>> seen(m, vector<bool>(n, false));
|
|
for (long i = 0; i < m; ++i) {
|
|
for (long j = 0; j < n; ++j) {
|
|
cin >> x; vault[i][j] = make_tuple(x, MAX);
|
|
}
|
|
}
|
|
auto neighbors = [m,n](pos p) {
|
|
long i = get<0>(p), j = get<1>(p);
|
|
vector<pos> ns; ns.reserve(4);
|
|
if (i > 0) ns.push_back(make_tuple(i-1,j));
|
|
if (i < m-1) ns.push_back(make_tuple(i+1,j));
|
|
if (j > 0) ns.push_back(make_tuple(i,j-1));
|
|
if (j < n-1) ns.push_back(make_tuple(i,j+1));
|
|
return ns;
|
|
};
|
|
auto length = [&vault](pos a, pos b) {
|
|
auto d = get<0>(vault[get<0>(b)][get<1>(b)]) - get<0>(vault[get<0>(a)][get<1>(a)]);
|
|
return d <= 0 ? 0 : d;
|
|
};
|
|
priority_queue<tuple<long, pos>> q;
|
|
q.push(make_tuple(0, make_tuple(0, 0))); get<1>(vault[0][0]) = 0;
|
|
while (!q.empty()) {
|
|
auto u = get<1>(q.top()); q.pop();
|
|
long i = get<0>(u), j = get<1>(u);
|
|
auto & vu = vault[i][j];
|
|
// cerr << "(" << get<0>(u) << "," << get<1>(u) << ") " << endl;
|
|
if (seen[i][j]) continue;
|
|
for (auto & v : neighbors(u)) {
|
|
auto & vv = vault[get<0>(v)][get<1>(v)];
|
|
auto d = max(get<1>(vu), length(u, v));
|
|
// cerr << "(" << get<0>(v) << "," << get<1>(v) << ") " << get<1>(vv) << " " << d << endl;
|
|
if (d < get<1>(vv)) {
|
|
get<1>(vv) = d; q.push(make_tuple(-d, v));
|
|
}
|
|
}
|
|
seen[i][j] = true;
|
|
}
|
|
// for (long i = 0; i < m; ++i) {
|
|
// for (long j = 0; j < n; ++j) {
|
|
// cerr << get<1>(vault[i][j]) << " ";
|
|
// }
|
|
// cerr << endl;
|
|
// }
|
|
cout << get<1>(vault[m-1][n-1]) << endl;
|
|
}
|