#include #include #include #include #include #include #include #include #include using namespace std; typedef struct{ int to; int cost; }edge; //SPFA //O(VE) //faster than bellman_ford algorithm void SPFA(vector> &G, vector &dist, int s){ const int INF = 1e8; fill(dist.begin(), dist.end(), INF); vector cnt(dist.size(), 0); dist[s] = 0; queue Q; auto my_push = [&](int node){ Q.push(node); cnt[node]++; }; auto my_pop = [&]() -> int{ int ret = Q.front(); cnt[ret]--; Q.pop(); return ret; }; my_push(s); while(!Q.empty()){ int pos = my_pop(); for(edge& E : G[pos]){ if(dist[ E.to ] > dist[ pos ] + E.cost ){ dist[ E.to ] = dist[ pos ] + E.cost; if(cnt[ E.to ] == 0){ my_push( E.to ); } } } } } void add_edge(vector > &G, int from, int to, int cost){ G[from].push_back( (edge){to, cost} ); //G[to].push_back( (edge){from, cost} ); } bool is_kadomatsu_sec(int a, int b, int c){ if(a==b || b==c || c==a) return false; if(ba && b>c) return true; return false; } int x[] = {0,1,0,-1}; int y[] = {-1,0,1,0}; int main(){ int w,h; cin >> w >> h; vector > v(h, vector(w)); for(int i=0; i> v[i][j]; } } vector > G(w*h*4); for(int i=0; i=w) continue; if(yy<0 || yy>=h) continue; for(int l=0; l<4; l++){ if(l==k) continue; int xxx = j+x[l]; int yyy = i+y[l]; if(xxx<0 || xxx>=w) continue; if(yyy<0 || yyy>=h) continue; if(is_kadomatsu_sec(v[yy][xx], v[i][j], v[yyy][xxx])){ add_edge(G, i*w+j + w*h*k, yyy*w+xxx + w*h*((l+2)%4), 1); } } } } } const int INF = 10000000; int ans = INF; vector dist(w*h*4); for(int i=0; i<4; i++){ int x1 = 0+x[i]; int y1 = 0+y[i]; if(x1<0 || x1>=w) continue; if(y1<0 || y1>=h) continue; for(int j=0; j<4; j++){ int x2 = x1+x[j]; int y2 = y1+y[j]; if(x2<0 || x2>=w) continue; if(y2<0 || y2>=h) continue; if(x2==0 && y2==0) continue; if(is_kadomatsu_sec(v[0][0], v[y1][x1], v[y2][x2])){ SPFA(G, dist, y2*w+x2 + w*h*((j+2)%4)); for(int k=0; k<4; k++){ ans = min(ans, dist[ (h-1)*w+(w-1) + w*h*k ]+2); } } } } if(ans < INF) cout << ans << endl; else cout << -1 << endl; return 0; }