#include //#include using namespace std; //using namespace std::chrono; #pragma GCC optimize("O3") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma,tune=native") typedef long long lld; typedef double lf; typedef long double llf; typedef pair pii; typedef pair pll; #define For(i,s,a) for(int i = (int)s; i < (int)a; ++i) #define rpt(s, it) for(auto it = s.begin(); it != s.end(); ++it) #define brpt(s, it) for(auto it = s.rend(); it != s.rbegin(); --it) #define sz size() #define pb push_back #define eb emplace_back #define ff first #define dd second #define mp make_pair #define all(x) (x).begin(), (x).end() #define make_unique(x) (x).erase( unique(all(x)), (x).end()) #define popcnt(x) __builtin_popcount(x) #define time_since duration_cast(system_clock::now().time_since_epoch()) template ostream & operator <<(ostream & os, pair x){ return os << x.ff << " " << x.dd; } const int N = 3e5 + 1; vector>field; vector>graph[N]; double odl[N]; const double eps = 0.0000001; priority_queue>R; void dij(int x) { odl[x] = 0; R.push({0, x}); while(!R.empty()) { x = R.top().dd; R.pop(); for(auto s : graph[x]) if(odl[s.dd] - odl[x] - s.ff > eps) { odl[s.dd] = odl[x] + s.ff; R.push({-odl[s.dd], s.dd}); } } } void solve(void) { double sq2 = sqrt(2) * 2; int w, h; scanf("%d%d", &w, &h); /*w = 50000; h = 2; */field = vector>(h, vector(w)); pii s, t; scanf("%d%d%d%d", &s.ff, &s.dd, &t.ff, &t.dd); /*s.ff = s.dd = 1; t.ff = 49998; t.dd = 1; *///puts(""); For(i, 0, h / 2) For(j, 0, w / 2) { scanf("%d", &field[i][j]); //field[i][j] = 1; int lg = i * 2 * w + j * 2; int rg = i * 2 * w + j * 2 + 1; int ld = i * 2 * w + j * 2 + w; int rd = i * 2 * w + j * 2 + w + 1; lg *= 2; rg *= 2; ld *= 2; rd *= 2; graph[lg + 1].pb({2, rg}); graph[rg + 1].pb({2, lg}); graph[ld + 1].pb({2, rd}); graph[rd + 1].pb({2, ld}); graph[lg + 1].pb({2, ld}); graph[ld + 1].pb({2, lg}); graph[rg + 1].pb({2, rd}); graph[rd + 1].pb({2, rg}); graph[lg + 1].pb({sq2, rd}); graph[rd + 1].pb({sq2, lg}); graph[rg + 1].pb({sq2, ld}); graph[ld + 1].pb({sq2, rg}); if(s.ff / 2 == j && s.dd / 2 == i) { graph[w * h * 2].pb({sq2 / 2.0, lg}); graph[w * h * 2].pb({sq2 / 2.0, rg}); graph[w * h * 2].pb({sq2 / 2.0, ld}); graph[w * h * 2].pb({sq2 / 2.0, rd}); } if(t.ff / 2 == j && t.dd / 2 == i) { graph[lg + 1].pb({sq2 / 2.0, w * h * 2 + 1}); graph[rg + 1].pb({sq2 / 2.0, w * h * 2 + 1}); graph[ld + 1].pb({sq2 / 2.0, w * h * 2 + 1}); graph[rd + 1].pb({sq2 / 2.0, w * h * 2 + 1}); } //cout<= wx[2]) graph[lg].pb({0, lg + 1}), graph[lg + 1].pb({0, lg}); int wa[4] = {field[i][j], i ? field[i - 1][j] : -1, j < w / 2 - 1 ? field[i][j + 1] : 0, i && j < w / 2 - 1 ? field[i - 1][j + 1] : 0}; sort(wa, wa + 4); if(field[i][j] >= wa[2]) graph[rg].pb({0, rg + 1}), graph[rg + 1].pb({0, rg}); int wb[4] = {field[i][j], i < h / 2 - 1 ? field[i + 1][j] : -1, j ? field[i][j - 1] : 0, i < h / 2 - 1 && j ? field[i + 1][j - 1] : 0}; sort(wb, wb + 4); if(field[i][j] >= wb[2]) graph[ld].pb({0, ld + 1}), graph[ld + 1].pb({0, ld}); int wc[4] = {field[i][j], i < h / 2 - 1 ? field[i + 1][j] : -1, j < w / 2 - 1 ? field[i][j + 1] : 0, i < h / 2 - 1 && j < w / 2 - 1 ? field[i + 1][j + 1] : 0}; sort(wc, wc + 4); if(field[i][j] >= wc[2]) graph[rd].pb({0, rd + 1}), graph[rd + 1].pb({0, rd}); // cout<= wx[2]) graph[lg + (field[i - 1][j] < wx[2])].pb({abs(field[i][j] - field[i - 1][j]), lgg * 2 + 1}); graph[rg + (field[i - 1][j] < wa[2])].pb({abs(field[i][j] - field[i - 1][j]), rgg * 2}); if(field[i][j] >= wa[2]) graph[rg + (field[i - 1][j] < wa[2])].pb({abs(field[i][j] - field[i - 1][j]), rgg * 2 + 1}); } if(j) { graph[lg + (field[i][j - 1] < wx[2])].pb({abs(field[i][j] - field[i][j - 1]), lgl * 2}); if(field[i][j] >= wx[2]) graph[lg + (field[i][j - 1] < wx[2])].pb({abs(field[i][j] - field[i][j - 1]), lgl * 2 + 1}); graph[ld + (field[i][j - 1] < wb[2])].pb({abs(field[i][j] - field[i][j - 1]), ldl * 2}); if(field[i][j] >= wb[2]) graph[ld + (field[i][j - 1] < wb[2])].pb({abs(field[i][j] - field[i][j - 1]), ldl * 2 + 1}); } if(j < w / 2 - 1) { graph[rg + (field[i][j + 1] < wa[2])].pb({abs(field[i][j] - field[i][j + 1]), rgr * 2}); if(field[i][j] >= wa[2]) graph[rg + (field[i][j + 1] < wa[2])].pb({abs(field[i][j] - field[i][j + 1]), rgr * 2 + 1}); graph[rd + (field[i][j + 1] < wc[2])].pb({abs(field[i][j] - field[i][j + 1]), rdr * 2}); if(field[i][j] >= wc[2]) graph[rd + (field[i][j + 1] < wc[2])].pb({abs(field[i][j] - field[i][j + 1]), rdr * 2 + 1}); } if(i < h / 2 - 1) { graph[ld + (field[i + 1][j] < wb[2])].pb({abs(field[i][j] - field[i + 1][j]), ldd * 2}); if(field[i][j] >= wb[2]) graph[ld + (field[i + 1][j] < wb[2])].pb({abs(field[i][j] - field[i + 1][j]), ldd * 2 + 1}); //cout<<" test "<= wc[2]) graph[rd + (field[i + 1][j] < wc[2])].pb({abs(field[i][j] - field[i + 1][j]), rdd * 2 + 1}); } } /*For(x, 0, w * h * 2 + 3) { cout<