#include using namespace std; /*/ #include using namespace atcoder; //*/ #define rep(i,n) for(int i=0;i; using ll = long long; using ull = unsigned long long; //*/ template inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } typedef pair pii; typedef pair pll; typedef vector vll; typedef vector vint; random_device rnd; mt19937 rng(rnd()); int dx[4] = {0,1,0,-1}; int dy[4] = {1,0,-1,0}; void solve(){ int h,w; cin >> h >> w; vector a(h,vll(w)); rep(i,h)rep(j,w) cin >> a[i][j]; vector c(h,vll(w,0)); priority_queue>,vector>>,greater>>> z,o; int var = 1; int ans = 0; set> zz,oo; oo.insert(make_pair(0,0)); zz.insert(make_pair(h-1,w-1)); c[0][0] = 1; c[h-1][w-1] = -1; rep(i,4){ if(dx[i] >= 0 && dy[i] >= 0) o.push(make_pair(a[dx[i]][dy[i]],make_pair(dx[i],dy[i]))); } rep(i,4){ if(dx[i] <= 0 && dy[i] <= 0) z.push(make_pair(a[h-1+dx[i]][w-1+dy[i]],make_pair(h-1+dx[i],w-1+dy[i]))); } while(1){ bool bre = false; ans++; if(var == 1){ auto pp = o.top(); o.pop(); auto [_,p] = pp; rep(i,4){ int ni = p.first+dx[i]; int nj = p.second+dy[i]; if(ni < 0 || nj < 0 || ni >= h || nj >= w || c[ni][nj] == var) continue; if(c[ni][nj] == -1) bre = true; else{ if(oo.find(make_pair(ni,nj)) == oo.end()) o.push(make_pair(a[ni][nj],make_pair(ni,nj))); oo.insert(make_pair(ni,nj)); } } c[p.first][p.second] = var; }else{ auto pp = z.top(); z.pop(); auto [_,p] = pp; rep(i,4){ int ni = p.first+dx[i]; int nj = p.second+dy[i]; if(ni < 0 || nj < 0 || ni >= h || nj >= w || c[ni][nj] == var) continue; if(c[ni][nj] == 1) bre = true; else{ if(zz.find(make_pair(ni,nj)) == zz.end()) z.push(make_pair(a[ni][nj],make_pair(ni,nj))); zz.insert(make_pair(ni,nj)); } } c[p.first][p.second] = var; } var *= -1; if(bre){ ans = 0; rep(i,h){ rep(j,w){ if(c[i][j] != 0) ans++; } } cout << ans-2 << endl; return; } } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int t = 1; //cin >> t; rep(dirc,t) solve(); }