#include<iostream> #include<set> #include<algorithm> #include<vector> #include<string> #include<set> #include<map> #include<numeric> #include<queue> #include<tuple> #include<cmath> using namespace std; typedef long long ll; const ll INF=1LL<<60; typedef pair<ll,int> P; typedef pair<int,P> PP; const ll MOD=1e9+7; //const int dx[]={-1,0,1,0}; //const int dy[]={0,-1,0,1}; const int dx[]={-1,0,1,1,1,0,-1,-1}; const int dy[]={-1,-1,-1,0,1,1,1,0}; struct edge{ int to; ll cost; edge(int to_,ll cost_):to(to_),cost(cost_){}; }; int main(){ int H,W; cin>>H>>W; vector<vector<ll>> A(H-1-2+1,vector<ll>(W,-1)); for(int i=0;i<H-2;i++){ for(int j=0;j<W;j++){ cin>>A[i][j]; } } vector<vector<edge>> G(H*W); for(int i=0;i<H-2;i++){ for(int j=0;j<W;j++){ if(A[i][j]==-1) continue; for(int k=0;k<8;k++){ int toi=dy[k]+i; int toj=dx[k]+j; if(toi<0 || H-2<=toi || toj<0 || W<=toj) continue; if(A[toi][toj]<0) continue; int now=i*W+j; int to=toi*W+toj; G[now].emplace_back(to,A[i][j]); } } } int start=(H-2)*W; int end=(H-2)*W+1; for(int i=0;i<H-2;i++){ G[start].emplace_back(i*W,0); if(A[i][W-1]>=0){ G[i*W+(W-1)].emplace_back(end,A[i][W-1]); } } //dijkstra vector<ll> dp(H*W,INF); priority_queue<P,vector<P>,greater<P>> pq; pq.emplace(0,start); while(!pq.empty()){ auto [cost,now]=pq.top(); pq.pop(); if(dp[now]<=cost) continue; //dp[now]>cost dp[now]=cost; for(edge e:G[now]){ if(dp[e.to]>(dp[now]+e.cost)){ pq.emplace(dp[now]+e.cost,e.to); } } } cout<<(dp[end]==INF?-1:dp[end])<<endl; /* for(int i=0;i<H-2;i++){ for(int j=0;j<W;j++){ cout<<"dp["<<i<<"]["<<j<<"]="<<dp[i*W+j]<<' '; } cout<<endl; } */ }